Wann hat ax + by = c ganzzahlige Lösungen?
Eine diophantische Gleichung ist eine Gleichung, deren Lösungen ganze Zahlen sein müssen. Der lineare Fall mit zwei Unbekannten geht auf Diophant von Alexandria zurück und ist vollständig gelöst. Die Gleichung ax + by = c hat genau dann ganzzahlige Lösungen, wenn der größte gemeinsame Teiler von a und b die Zahl c teilt. Ist das nicht der Fall, gibt es keine einzige Lösung, auch wenn reelle Lösungen natürlich unendlich viele existieren.
Der Grund liegt im Lemma von Bézout: Für den ggT g von a und b gibt es ganze Zahlen s und t mit a·s + b·t = g. Multipliziert man diese Gleichung mit c/g, erhält man sofort eine Lösung von ax + by = c. Umgekehrt ist a·x + b·y für ganze x und y immer ein Vielfaches von g, sodass c ohne Teilbarkeit nicht erreichbar ist.
Die Bézout-Koeffizienten s und t liefert der erweiterte euklidische Algorithmus. Er führt neben den fortlaufenden Divisionen mit Rest zwei Hilfsfolgen mit, aus denen am Ende s und t abzulesen sind. Die Zahl der Schritte wächst nur logarithmisch mit der Größe der Zahlen, das Verfahren ist deshalb auch für große Koeffizienten schnell. Die Darstellung folgt der Standardliteratur zur elementaren Zahlentheorie.
Allgemeine Lösung und praktische Beispiele
Ist eine Lösung (x0, y0) gefunden, erhält man alle anderen, indem man x um Vielfache von b/g erhöht und y gleichzeitig um dieselben Vielfachen von a/g verringert. Die Summe a·x + b·y bleibt dabei unverändert. Der Rechner normiert die spezielle Lösung so, dass x die kleinste nicht negative Zahl ist. Die direkt aus den Bézout-Koeffizienten berechnete Lösung wird zusätzlich angezeigt, sie hat oft große Beträge.
Viele Alltagsaufgaben führen auf diese Gleichung. Wie kann man 100 Euro genau mit Scheinen zu 7 und 11 Euro bezahlen? Wie viele Kisten zu 6 und zu 15 Flaschen ergeben genau 81 Flaschen? Hier interessieren nur Lösungen mit x und y nicht negativ. Haben a und b dasselbe Vorzeichen, ist ihre Anzahl endlich, und der Rechner zählt sie. Bei unterschiedlichen Vorzeichen gibt es unendlich viele.
Ein bekanntes Ergebnis ist der Satz von Sylvester zum Münzproblem: Sind a und b positiv und teilerfremd, lässt sich jede ganze Zahl größer als ab − a − b als nicht negative Kombination darstellen. Bei Münzen zu 7 und 11 ist 59 der größte Betrag, der nicht passend bezahlt werden kann. Mit dem Rechner lässt sich das für 59 und 60 schnell überprüfen.
Die lineare diophantische Gleichung ist eng verwandt mit Kongruenzen. Die Gleichung ax + by = c ist gleichwertig zu ax ≡ c (mod b). Ist ggT(a, b) = 1, ist s die modulare Inverse von a modulo b. Damit lassen sich lineare Kongruenzen lösen, wie sie etwa beim chinesischen Restsatz oder in der Kryptografie beim RSA-Verfahren auftreten. Der Rechner arbeitet mit Beträgen bis zehn Millionen exakt.
Tipps und typische Fehler
Ganzzahlig lösen.
- ggT: Zuerst prüfen.
- Kürzen: Durch den ggT.
- Probe: Einsetzen.
- Grenzen: Vorzeichen beachten.
Mehr zum Thema Gleichungen lösen
Häufige Fragen
Was ist eine diophantische Gleichung?
Eine Gleichung mit ganzzahligen Koeffizienten, für die nur ganzzahlige Lösungen gesucht werden. Der lineare Fall ax + by = c ist vollständig mit dem ggT lösbar.
Warum hat 6x + 9y = 7 keine Lösung?
Weil ggT(6, 9) = 3 ist und 6x + 9y deshalb immer durch 3 teilbar ist. Die 7 ist es nicht, also gibt es keine ganzzahligen x und y.
Wie viele Lösungen gibt es insgesamt?
Ist die Gleichung lösbar, gibt es unendlich viele ganzzahlige Lösungen. Mit x, y ≥ 0 sind es bei gleichen Vorzeichen von a und b nur endlich viele.
Was ist das Lemma von Bézout?
Für ganze Zahlen a und b gibt es ganze s und t mit a·s + b·t = ggT(a, b).
Was ist das Münzproblem von Frobenius?
Die Frage nach dem größten Betrag, der sich mit Münzen zu a und b nicht bezahlen lässt. Für teilerfremde a und b ist es ab − a − b.
- diophantische Gleichung lösen
- ax + by = c ganzzahlig
- erweiterter euklidischer Algorithmus
- Bézout-Koeffizienten
- lineare diophantische Gleichung
- ganzzahlige Lösungen berechnen
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.