Rechner für lineare diophantische Gleichungen

Q: Wie löse ich eine lineare diophantische Gleichung von Hand?

Berechnen Sie zuerst g = gcd(a, b) mit dem euklidischen Algorithmus. Teilt g die Zahl c nicht, gibt es keine ganzzahligen Lösungen. Andernfalls bestimmen Sie mit dem erweiterten euklidischen Algorithmus Bézout-Koeffizienten mit g = sa + tb, multiplizieren mit c/g und erhalten x_0 = s · c/g und y_0 = t · c/g; alle Lösungen schreiben Sie dann als x = x_0 + (b/g)t, y = y_0 - (a/g)t.

Q: Können negative Koeffizienten oder eine negative rechte Seite verwendet werden?

Ja, alle drei Eingaben dürfen negativ oder null sein — nur Brüche und Dezimalzahlen werden abgelehnt. Der ggT wird stets von den Beträgen gebildet und ist daher positiv. Die Formeln der allgemeinen Lösung funktionieren mit negativem a, b oder c unverändert; es ändern sich nur die Vorzeichen der Schrittweiten b/g und a/g in den Parameterformeln.

Q: Woran erkenne ich am schnellsten, dass keine Lösung existiert?

Prüfen Sie die Teilbarkeit durch den ggT: Lösungen existieren genau dann, wenn gcd(a,b) die Zahl c teilt. Ein schneller Paritätstest deckt viele Schulbuchfälle ab — sind a und b beide gerade, ist die linke Seite immer gerade, und ein ungerades c macht die Gleichung unlösbar. Ebenso ist 6x + 10y immer gerade und zudem immer nur ein Vielfaches von gcd(6,10)=2.

Q: Wie finde ich nur nicht-negative oder positive Lösungen?

Die Parameterfamilie x = x_0 + (b/g)t, y = y_0 - (a/g)t liefert Ihnen eine lineare Bedingung an t. Lösen Sie die beiden Ungleichungen x ≥ 0 und y ≥ 0 nach t auf, bilden Sie den Durchschnitt (ein endlicher Bereich ganzer Zahlen) und listen Sie jeden Wert auf. Bleibt dieser Bereich für t leer, existiert keine Lösung, in der beide Variablen nicht-negativ sind.

Q: Warum liefert der Rechner eine andere spezielle Lösung als mein Schulbuch?

Spezielle Lösungen sind nie eindeutig — passt (x_0, y_0), dann passt auch (x_0 + b/g, y_0 - a/g). Beide Antworten sind richtig, weil sie über den Parameter t dieselbe vollständige Lösungsmenge erzeugen. Dieser Rechner verschiebt x_0 in den kompakten Bereich 0 ≤ x_0 < |b/g|, was Schulbücher unter Umständen nicht tun. Prüfen Sie immer durch Einsetzen in ax + by.

Q: Was passiert, wenn a oder b gleich null ist?

Die Gleichung fällt auf eine einzige Variable zurück. Ist b = 0, muss a mid c gelten; dann ist x = c/a fest, während y beliebig ganz sein kann — und symmetrisch für a = 0. Sind beide Koeffizienten null, ist die Gleichung entweder immer erfüllt (c = 0, jedes Paar passt) oder nie. Der Rechner behandelt alle diese entarteten Fälle direkt.

Q: Worin unterscheidet sich das vom Lösen einer gewöhnlichen linearen Gleichung?

Über den reellen Zahlen hat ax + by = c mit einem von null verschiedenen Koeffizienten immer Lösungen — sogar eine ganze Gerade voller. Die diophantische Variante verlangt ausschließlich ganzzahlige Paare, wodurch die Gleichung unlösbar werden kann (wenn gcd(a,b) nmid c) oder statt eines Kontinuums eine diskrete, gleichmäßig verteilte Lösungsmenge auf dieser Geraden liefert. Der Abstand zwischen aufeinanderfolgenden Lösungen beträgt genau (b/g, -a/g).

Aktualisiert: 15 Oktober 2026

Löst die lineare diophantische Gleichung ax + by = c in ganzen Zahlen. Geben Sie die Koeffizienten a, b und c ein, um zu prüfen, ob Lösungen existieren, eine spezielle Lösung zu erhalten sowie die vollständige Lösungsfamilie x = x₀ + (b/g)t, y = y₀ − (a/g)t.

Gleichung ax + by = c in ganzen Zahlen lösen

Formel der linearen diophantischen Gleichung

Formel

\[ ax + by = c, \qquad a, b, c \in \mathbb{Z} \] \[ g = \gcd(a, b) \] \[ \text{Ganzzahlige Lösungen existieren} \iff g \mid c \] \[ x = x_0 + \frac{b}{g}\,t, \qquad y = y_0 - \frac{a}{g}\,t, \qquad t \in \mathbb{Z} \]

Dabei gilt:

\(a\), \(b\) — ganze Koeffizienten von \(x\) und \(y\)
\(c\) — die ganze Zahl auf der rechten Seite
\(g = \gcd(a, b)\) — der größte gemeinsame Teiler der Koeffizienten
\((x_0, y_0)\) — eine spezielle Lösung, die aus der Bézout-Identität \(g = s\,a + t\,b\) durch Multiplikation mit \(c/g\) hervorgeht
\(t\) — ein beliebiger ganzzahliger Parameter, der alle Lösungen erzeugt

Die Gleichung besitzt genau dann ganzzahlige Lösungen, wenn \(\gcd(a,b)\) die Zahl \(c\) teilt. Ist das der Fall, gibt es unendlich viele davon: Ausgehend von einer Lösung \((x_0, y_0)\) entsteht jede weitere Lösung, indem man \(x\) insgesamt \(t\)-mal um \(b/g\) erhöht und \(y\) um \(a/g\) erniedrigt.

Lineare diophantische Gleichung – Rechenbeispiel

Beispiel: Lösen Sie \(12x + 18y = 30\) in ganzen Zahlen (mit den Voreinstellungen des Rechners).

\[ \gcd(12, 18): \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0 \implies \gcd(12, 18) = 6 \]

\[ 6 \mid 30 \implies \text{Lösungen existieren} \]

\[ \text{Bézout: } 6 = (-1) \cdot 12 + 1 \cdot 18, \qquad \frac{c}{g} = \frac{30}{6} = 5 \]

\[ x_0 = -1 \cdot 5 = -5, \qquad y_0 = 1 \cdot 5 = 5 \]

\[ 12 \cdot (-5) + 18 \cdot 5 = -60 + 90 = 30 \;\checkmark \]

Verschiebt man \(x_0\) in den Bereich \(0 \le x < |b/g| = 3\), erhält man die gleichwertige spezielle Lösung \((1, 1)\), denn \(12 \cdot 1 + 18 \cdot 1 = 30\).

Ergebnis: Alle ganzzahligen Lösungen lauten \(x = 1 + 3t\), \(y = 1 - 2t\) mit beliebigem ganzzahligen \(t\); zum Beispiel \((1, 1)\), \((4, -1)\), \((-2, 3)\).

So benutzen Sie den Rechner

Geben Sie den ganzzahligen Koeffizienten von \(x\) in das Feld Koeffizient von x (a) ein.
Geben Sie den ganzzahligen Koeffizienten von \(y\) in das Feld Koeffizient von y (b) ein.
Geben Sie die rechte Seite in das Feld Rechte Seite (c) ein.
Lesen Sie die Ergebnisblöcke ab: Existieren ganzzahlige Lösungen? zeigt Ihnen, ob \(\gcd(a,b)\) die Zahl \(c\) teilt; Eine Lösung (x₀, y₀) liefert eine geprüfte spezielle Lösung; Allgemeine ganzzahlige Lösung gibt die vollständige Lösungsfamilie mit dem Parameter \(t\) an; Lösungsschritte zeigt den euklidischen Algorithmus, die Bézout-Koeffizienten und die Herleitung.

Alle drei Eingaben müssen ganze Zahlen sein (positiv, negativ oder null). Bei einer nicht-ganzzahligen Eingabe fordert der Rechner eine ganze Zahl an, denn diophantische Gleichungen werden definitionsgemäß ausschließlich in ganzen Zahlen gelöst.

Was ist eine lineare diophantische Gleichung?

Eine diophantische Gleichung ist eine Gleichung, deren Lösungen ganze Zahlen sein müssen. Die lineare diophantische Gleichung \(ax + by = c\) ist die einfachste Form: Gesucht sind alle ganzzahligen Paare \((x, y)\), die sie exakt erfüllen — Brüche und Dezimalzahlen sind nicht erlaubt. Solche Gleichungen treten überall dort natürlich auf, wo Mengen unteilbar sind — Münzen fester Stückwerte, Kartons mit Ware, Personen oder Fliesen.

Der zentrale Sachverhalt ist die Lösbarkeitsbedingung: \(ax + by\) ist stets ein Vielfaches von \(\gcd(a, b)\), also muss auch \(c\) ein Vielfaches von \(\gcd(a, b)\) sein. So ist \(6x + 10y\) zum Beispiel immer gerade, weshalb \(6x + 10y = 7\) keine ganzzahligen Lösungen hat, so lange man auch sucht. Ist die Bedingung erfüllt, garantiert die Bézout-Identität mindestens eine Lösung, die der erweiterte euklidische Algorithmus effizient findet.

Die Interpretation des Ergebnisses: Existieren Lösungen, gibt es unendlich viele davon, angeordnet in einer arithmetischen Folge. Die allgemeine Lösung \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) umfasst sie alle — jeder Schritt des Parameters \(t\) erhöht \(x\) um \(b/g\) und verringert \(y\) um \(a/g\), wobei \(ax + by\) unverändert bleibt. Benötigen Sie Lösungen in einem bestimmten Bereich (etwa nicht-negative), setzen Sie einige Werte für \(t\) ein und behalten die passenden.

Voraussetzungen, Grenzen und Hinweise

Nur ganze Zahlen. Die Koeffizienten müssen ganze Zahlen sein; die Gleichung wird nicht über den rationalen oder reellen Zahlen gelöst. Über den reellen Zahlen hat \(ax + by = c\) bei einem von null verschiedenen \(a\) oder \(b\) immer Lösungen — erst die Beschränkung auf ganze Zahlen macht das Problem interessant.
Größenbeschränkung. Die Berechnung verwendet Standard-Arithmetik; halten Sie die Koeffizienten daher im sicheren Ganzzahlbereich (etwa bis zu 15 Stellen), um Genauigkeitsprobleme zu vermeiden.
Entartete Fälle werden behandelt. Ist \(a = b = 0\), ist die Gleichung entweder immer erfüllt (\(c = 0\), jedes Paar passt) oder nie. Ist genau ein Koeffizient null, hat die Gleichung nur noch eine Variable, die der Rechner direkt auflöst.
Jede spezielle Lösung ist gültig. Das Paar \((x_0, y_0)\) ist nicht eindeutig — der Rechner verschiebt es in eine kompakte Form mit \(0 \le x_0 < |b/g|\), aber jede Wahl erzeugt über den Parameter \(t\) dieselbe vollständige Lösungsmenge.
Antwort prüfen. Kontrollieren Sie das Ergebnis immer durch Einsetzen: Berechnen Sie \(a x_0 + b y_0\) und vergewissern Sie sich, dass \(c\) herauskommt. Diese Prüfung führt der Rechner in der Ausgabe für Sie durch.

Geht es in Ihrer Aufgabe um zwei lineare Gleichungen gleichzeitig, also um ein System wie \(ax + by = c\), \(dx + ey = f\), wird dieses mit der Eliminationsmethode gelöst und nicht über die Teilbarkeit durch den ggT. Diophantisches Denken steckt auch hinter Themen wie der direkten Proportionalität, bei denen zwei ganzzahlige Größen in festem Verhältnis wachsen, und es ist ein klassisches Werkzeug in Wettbewerbs- und zahlentheoretischen Aufgaben.

Häufig gestellte Fragen

Wie löse ich eine lineare diophantische Gleichung von Hand?

Berechnen Sie zuerst \(g = \gcd(a, b)\) mit dem euklidischen Algorithmus. Teilt \(g\) die Zahl \(c\) nicht, gibt es keine ganzzahligen Lösungen. Andernfalls bestimmen Sie mit dem erweiterten euklidischen Algorithmus Bézout-Koeffizienten mit \(g = sa + tb\), multiplizieren mit \(c/g\) und erhalten \(x_0 = s \cdot c/g\) und \(y_0 = t \cdot c/g\); alle Lösungen schreiben Sie dann als \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\).

Können negative Koeffizienten oder eine negative rechte Seite verwendet werden?

Ja, alle drei Eingaben dürfen negativ oder null sein — nur Brüche und Dezimalzahlen werden abgelehnt. Der ggT wird stets von den Beträgen gebildet und ist daher positiv. Die Formeln der allgemeinen Lösung funktionieren mit negativem \(a\), \(b\) oder \(c\) unverändert; es ändern sich nur die Vorzeichen der Schrittweiten \(b/g\) und \(a/g\) in den Parameterformeln.

Woran erkenne ich am schnellsten, dass keine Lösung existiert?

Prüfen Sie die Teilbarkeit durch den ggT: Lösungen existieren genau dann, wenn \(\gcd(a,b)\) die Zahl \(c\) teilt. Ein schneller Paritätstest deckt viele Schulbuchfälle ab — sind \(a\) und \(b\) beide gerade, ist die linke Seite immer gerade, und ein ungerades \(c\) macht die Gleichung unlösbar. Ebenso ist \(6x + 10y\) immer gerade und zudem immer nur ein Vielfaches von \(\gcd(6,10)=2\).

Wie finde ich nur nicht-negative oder positive Lösungen?

Die Parameterfamilie \(x = x_0 + (b/g)t\), \(y = y_0 - (a/g)t\) liefert Ihnen eine lineare Bedingung an \(t\). Lösen Sie die beiden Ungleichungen \(x \ge 0\) und \(y \ge 0\) nach \(t\) auf, bilden Sie den Durchschnitt (ein endlicher Bereich ganzer Zahlen) und listen Sie jeden Wert auf. Bleibt dieser Bereich für \(t\) leer, existiert keine Lösung, in der beide Variablen nicht-negativ sind.

Warum liefert der Rechner eine andere spezielle Lösung als mein Schulbuch?

Spezielle Lösungen sind nie eindeutig — passt \((x_0, y_0)\), dann passt auch \((x_0 + b/g,\; y_0 - a/g)\). Beide Antworten sind richtig, weil sie über den Parameter \(t\) dieselbe vollständige Lösungsmenge erzeugen. Dieser Rechner verschiebt \(x_0\) in den kompakten Bereich \(0 \le x_0 < |b/g|\), was Schulbücher unter Umständen nicht tun. Prüfen Sie immer durch Einsetzen in \(ax + by\).

Was passiert, wenn a oder b gleich null ist?

Die Gleichung fällt auf eine einzige Variable zurück. Ist \(b = 0\), muss \(a \mid c\) gelten; dann ist \(x = c/a\) fest, während \(y\) beliebig ganz sein kann — und symmetrisch für \(a = 0\). Sind beide Koeffizienten null, ist die Gleichung entweder immer erfüllt (\(c = 0\), jedes Paar passt) oder nie. Der Rechner behandelt alle diese entarteten Fälle direkt.

Worin unterscheidet sich das vom Lösen einer gewöhnlichen linearen Gleichung?

Über den reellen Zahlen hat \(ax + by = c\) mit einem von null verschiedenen Koeffizienten immer Lösungen — sogar eine ganze Gerade voller. Die diophantische Variante verlangt ausschließlich ganzzahlige Paare, wodurch die Gleichung unlösbar werden kann (wenn \(\gcd(a,b) \nmid c\)) oder statt eines Kontinuums eine diskrete, gleichmäßig verteilte Lösungsmenge auf dieser Geraden liefert. Der Abstand zwischen aufeinanderfolgenden Lösungen beträgt genau \((b/g, -a/g)\).