Rechner · Klasse 9 bis Studium
Rechner für diophantische Gleichungen ax + by = c
Der Rechner findet alle ganzzahligen Lösungen einer Gleichung ax + by = c. Er zeigt den erweiterten euklidischen Algorithmus als Tabelle, prüft mit dem ggT, ob es überhaupt Lösungen gibt, und listet die Lösungen ohne negative Zahlen auf.
Kostenlos für Unterricht und Lernen (Bedingungen). Im Unterricht ohne Werbung: Unterrichtsansicht · Sie unterrichten?
So benutzt du den Rechner
Gib die drei ganzen Zahlen a, b und c der Gleichung a · x + b · y = c ein. Negative Zahlen sind erlaubt, nur a und b dürfen nicht beide 0 sein. Der Rechner sucht ganze Zahlen x und y, die die Gleichung erfüllen. Brüche und Kommazahlen zählen nicht als Lösung, genau das unterscheidet eine diophantische Gleichung von einer gewöhnlichen.
Wann gibt es eine Lösung?
Die Gleichung a · x + b · y = c hat genau dann ganzzahlige Lösungen, wenn der größte gemeinsame Teiler von a und b auch c teilt. Der Grund ist einfach: Wenn d sowohl a als auch b teilt, dann teilt d auch jede Summe a · x + b · y. Bei 6x + 9y = 20 ist der ggT 3. Die linke Seite ist also immer ein Vielfaches von 3, die 20 aber nicht. Es gibt keine Lösung.
Der Rechenweg an einem Beispiel
Mit Briefmarken zu 7 Cent und 5 Cent soll ein Brief genau 100 Cent Porto bekommen. Gesucht sind also ganze Zahlen mit 7x + 5y = 100.
Die Tabelle des Rechners führt in jeder Zeile einen Rest r und zwei Zahlen s und t mit r = a · s + b · t. Die erste Zeile ist a selbst (s = 1, t = 0), die zweite b (s = 0, t = 1). Jede weitere Zeile entsteht aus den beiden darüber: Man teilt mit Rest und zieht das Vielfache ab, bei s und t genauso wie bei r. Die letzte Zeile vor dem Rest 0 enthält den ggT und dazu die passenden Faktoren s und t.
Alle Lösungen und die mit positiven Zahlen
Hat man eine Lösung x₀, y₀ gefunden, erhält man alle anderen mit x = x₀ + (b : d) · t und y = y₀ − (a : d) · t, wobei d der ggT ist und t jede ganze Zahl sein darf. Ganzzahlige Lösungen gibt es also unendlich viele, sobald es eine gibt. In Sachaufgaben zählen aber meist nur Anzahlen, die nicht negativ sind. Sind a und b beide positiv, gibt es davon nur endlich viele, und der Rechner listet bis zu 30 auf. Haben a und b verschiedene Vorzeichen, gibt es auch unendlich viele Lösungen mit x ≥ 0 und y ≥ 0.
Die Theorie dahinter mit weiteren Beispielen und Übungen steht auf der Lernseite Diophantische Gleichungen. Den ggT allein bestimmt der ggT- und kgV-Rechner, Kongruenzen wie 7x ≡ 100 (mod 5) löst der Modulo-Rechner.
Häufige Fragen
Was ist eine diophantische Gleichung?
Eine Gleichung mit ganzzahligen Koeffizienten, für die man nur ganzzahlige Lösungen sucht. Die einfachste Form ist die lineare Gleichung a · x + b · y = c mit zwei Unbekannten.
Wie löst man eine diophantische Gleichung?
Man bestimmt mit dem erweiterten euklidischen Algorithmus den ggT d von a und b und Zahlen s, t mit a · s + b · t = d. Teilt d die Zahl c, multipliziert man s und t mit c : d und erhält eine Lösung. Alle weiteren entstehen, indem man b : d zu x addiert und a : d von y abzieht.
Warum hat 6x + 9y = 20 keine Lösung?
Die linke Seite ist für ganze x und y immer durch 3 teilbar, weil 6 und 9 es sind. Die 20 ist nicht durch 3 teilbar.
Kann der Rechner auch Gleichungen mit drei Unbekannten lösen?
Nein, er löst Gleichungen mit zwei Unbekannten. Bei drei Unbekannten hält man eine fest, löst die übrige Gleichung mit zwei Unbekannten und probiert die festgehaltene Zahl der Reihe nach durch.
Fehler entdeckt oder einen Wunsch? Schreib uns eine kurze Nachricht, wir kümmern uns darum.
Weiterlesen
Diophantische Gleichungen
Bei einer diophantischen Gleichung zählen nur ganze Zahlen als Lösung. Hier löst du ax + by = c Schritt für Schritt mit dem erweiterten euklidischen…
ca. 200–284 n. Chr. Diophant von Alexandria
Diophant von Alexandria löste Zahlenaufgaben mit einer frühen Form der Algebra. Seine Arithmetica führte über Fermats berühmte Randnotiz bis zu…
Klasse 5–6 bis Studium