Diophantische Gleichungen

Eine diophantische Gleichung ist eine Gleichung, bei der nur ganze Zahlen als Lösung zählen, zum Beispiel 3x + 5y = 28 mit ganzzahligen x und y. Das Paar x = 6, y = 2 passt, denn 18 + 10 = 28. Das Paar x = 2, y = 4,4 erfüllt die Gleichung ebenfalls, zählt aber nicht, weil 4,4 keine ganze Zahl ist.

Der Name erinnert an Diophant von Alexandria (3. Jahrhundert), der meist rationale Lösungen suchte. Heute braucht man ganzzahlige Lösungen für Briefmarken, Münzen, Stückzahlen und für die modulare Inverse in der Kryptologie. Hier löst du die lineare Form ax + by = c und lernst am Ende schwerere Typen kennen. Zum Nachrechnen gibt es den Rechner für diophantische Gleichungen.

Was ist eine diophantische Gleichung?

Briefmarken und Tiere

Briefmarken: Ein Brief soll mit Marken zu 3 und zu 5 Cent genau 28 Cent Porto tragen. Mit x Marken zu 3 Cent und y Marken zu 5 Cent gilt 3x + 5y = 28. Bei kleinen Zahlen probierst du y durch. Nach Abzug von 5y muss ein Vielfaches von 3 bleiben:

Es gibt zwei Möglichkeiten: 6 Marken zu 3 Cent und 2 zu 5 Cent oder 1 Marke zu 3 Cent und 5 zu 5 Cent.

Hühner und Kaninchen: Hühner haben 2 Beine, Kaninchen 4. Aus 20 Beinen folgt 2h + 4k = 20 mit sechs Möglichkeiten, von 10 Hühnern ohne Kaninchen bis zu 5 Kaninchen ohne Huhn. Eine zweite Angabe macht die Lösung eindeutig: Im chinesischen Rechenbuch des Sunzi (3. bis 5. Jahrhundert) sind es 35 Köpfe und 94 Beine, also 23 Hühner und 12 Kaninchen. Das ist dann ein lineares Gleichungssystem.

Wann hat ax + by = c ganzzahlige Lösungen?

Der Grund in einer Richtung ist einfach: Teilt d sowohl a als auch b, dann teilt d jede Summe a · x + b · y. Bei 6x + 9y = 20 ist d = 3. Die linke Seite ist immer ein Vielfaches von 3, die 20 nicht, also gibt es keine Lösung. Dass es im anderen Fall immer eine gibt, zeigt der Algorithmus im nächsten Abschnitt.

Der erweiterte euklidische Algorithmus als Tabelle

Den euklidischen Algorithmus kennst du vom ggT. Die erweiterte Form führt zwei Spalten s und t mit, sodass in jeder Zeile gilt: r = a · s + b · t. So gehst du vor:

1. Die erste Zeile ist r = a, s = 1, t = 0. Die zweite Zeile ist r = b, s = 0, t = 1.
2. Teile die vorletzte Zeile durch die letzte: r_vor : r_letzte = q Rest …
3. Die neue Zeile ist r = r_vor − q · r_letzte, ebenso s = s_vor − q · s_letzte und t = t_vor − q · t_letzte.
4. Mach weiter, bis der Rest 0 ist. Die Zeile davor enthält den ggT d mit zugehörigen s und t.

Das stimmt in jeder Zeile, weil du mit r, s und t dieselbe Rechnung ausführst: Erfüllen zwei Zeilen die Gleichung r = a · s + b · t, erfüllt sie auch r_vor − q · r_letzte. Dasselbe Verfahren liefert die modulare Inverse.

Die letzte Zeile mit Rest 0 verrät die Schrittweiten für später: Ihre Zahlen s = 8 und t = −13 sind b/d und −a/d (bei einer geraden Zahl von Divisionen mit umgekehrtem Vorzeichen).

Beispiel: 13x + 8y = 100

Du willst mit Marken zu 13 und zu 8 Cent genau 100 Cent Porto kleben. Gesucht sind ganze x und y mit 13x + 8y = 100.

1. Lösbar? d = ggT(13, 8) = 1, und 1 teilt 100. Es gibt Lösungen.
2. Algorithmus: Aus der Tabelle folgt 13 · (−3) + 8 · 5 = 1.
3. Spezielle Lösung: Multipliziere mit c/d = 100: 13 · (−300) + 8 · 500 = 100. Also ist x₀ = −300 und y₀ = 500 eine Lösung. Als Marken ist sie sinnlos, mathematisch aber richtig.

Die allgemeine Lösung

Der Rechner nennt den Parameter t statt k. Warum das alle Lösungen sind: Erhöhst du x um b/d, wächst a · x um a · b/d. Senkst du y um a/d, sinkt b · y um denselben Betrag. Zwei Lösungen unterscheiden sich um Δx und Δy mit (a/d) · Δx = −(b/d) · Δy. Weil a/d und b/d keinen gemeinsamen Teiler haben, ist Δx ein Vielfaches von b/d.

Im Beispiel ist b/d = 8 und a/d = 13, also x = −300 + 8k und y = 500 − 13k.

Nur nicht negative Lösungen finden

Briefmarken kann man nicht negativ kaufen. Du brauchst x ≥ 0 und y ≥ 0. Das ergibt zwei Ungleichungen für k:

• x ≥ 0: −300 + 8k ≥ 0, also k ≥ 37,5, das heißt k ≥ 38.
• y ≥ 0: 500 − 13k ≥ 0, also k ≤ 38,46…, das heißt k ≤ 38.

Nur k = 38 erfüllt beides: x = 4 und y = 6. Probe: 13 · 4 + 8 · 6 = 52 + 48 = 100. Die Tabelle zeigt, wie das Vorzeichen wechselt.

Du klebst also 4 Marken zu 13 Cent und 6 Marken zu 8 Cent. Sind a und b positiv, gibt es nur endlich viele Lösungen mit x, y ≥ 0, je nach Gleichung keine, eine oder mehrere.

Zweites Beispiel: der ggT ist größer als 1

Ein Verein bestellt T-Shirts zu 21 € und Kappen zu 15 €. Die Rechnung beträgt genau 150 €. Gesucht sind ganze x und y mit 21x + 15y = 150.

Lösbar? d = ggT(21, 15) = 3, und 150 : 3 = 50. Es gibt Lösungen. Du darfst die Gleichung durch 3 teilen: 7x + 5y = 50 hat dieselben Lösungen. Die Tabelle liefert 21 · (−2) + 15 · 3 = 3.

Spezielle Lösung: Multipliziere mit c/d = 50. Dann ist x₀ = −100 und y₀ = 150. Probe: 21 · (−100) + 15 · 150 = −2.100 + 2.250 = 150.

Allgemeine Lösung: Es gilt b/d = 5 und a/d = 7, also x = −100 + 5k und y = 150 − 7k.

Nicht negativ: x ≥ 0 gibt k ≥ 20, y ≥ 0 gibt k ≤ 21,43…, also k ≤ 21.

Es bleiben k = 20 und k = 21: 0 T-Shirts und 10 Kappen oder 5 T-Shirts und 3 Kappen. Soll von beiden mindestens eins dabei sein, passt nur 5 und 3.

Mit dem Rechner prüfen

Der Rechner für diophantische Gleichungen zeigt dieselbe Tabelle mit Rest r, Quotient q, s und t, nennt die allgemeine Lösung und listet die Lösungen mit x, y ≥ 0 auf. Mit 13, 8 und 100 findest du x = 4 und y = 6 wieder.

Schwerere Verwandte: nichtlineare diophantische Gleichungen

Sobald Quadrate oder höhere Potenzen vorkommen, wird es schwer.

Pythagoreische Tripel

Die Gleichung x² + y² = z² hat unendlich viele ganzzahlige Lösungen, etwa (3, 4, 5), (5, 12, 13) und (8, 15, 17). Aus ganzen Zahlen m > n > 0 erhältst du sie mit x = m² − n², y = 2mn und z = m² + n². Für m = 2 und n = 1 entsteht (3, 4, 5). Die Geometrie dahinter steht beim Satz des Pythagoras.

Die Pellsche Gleichung

Die Gleichung x² − N · y² = 1 mit einer Zahl N, die keine Quadratzahl ist, hat immer unendlich viele Lösungen. Für N = 2 ist die kleinste (3, 2), denn 9 − 2 · 4 = 1. Für N = 61 sind es schon x = 1.766.319.049 und y = 226.153.980. Brahmagupta untersuchte sie im 7. Jahrhundert, Fermat stellte sie 1657 als Aufgabe, und Lagrange bewies als Erster, dass es immer Lösungen gibt. Ihren Namen verdankt sie einem Irrtum Eulers, der sie dem Engländer John Pell zuschrieb.

Fermats großer Satz

Die Gleichung xⁿ + yⁿ = zⁿ hat für n ≥ 3 keine Lösung in positiven ganzen Zahlen. Fermat behauptete das um 1637 am Rand seiner Arithmetica. Den Beweis lieferte Andrew Wiles: Er trug ihn 1993 vor, eine Lücke schloss er 1994 mit Richard Taylor, veröffentlicht wurde er 1995.

Hilberts zehntes Problem

David Hilbert fragte 1900 nach einem Verfahren, das für jede diophantische Gleichung entscheidet, ob sie ganzzahlige Lösungen hat. 1970 zeigte Juri Matijassewitsch, aufbauend auf Arbeiten von Martin Davis, Hilary Putnam und Julia Robinson, dass es kein solches Verfahren gibt. Für ax + by = c gibt es eines: den ggT-Test.

Typische Fehler

Übungen mit Lösungen

Woher die Gleichungen ihren Namen haben

Diophant lebte vermutlich im 3. Jahrhundert in Alexandria. In seiner Arithmetica löst er Aufgaben, bei denen Zahlen bestimmte Bedingungen erfüllen sollen, und lässt dabei Brüche zu (Diophant und die diophantischen Gleichungen, Hellenistische Mathematik). Systematische Verfahren für ganzzahlige Lösungen entwickelten später indische Mathematiker wie Aryabhata und Brahmagupta. In Europa griffen Fermat im 17. Jahrhundert sowie Euler und Lagrange im 18. Jahrhundert das Thema auf.

Häufige Fragen

Quellen und weiterführende Literatur

• G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers, 6. Auflage, Oxford University Press, Oxford 2008.
• Kenneth H. Rosen: Elementary Number Theory and Its Applications, 6. Auflage, Pearson, Boston 2011.
• Andrew Wiles: Modular elliptic curves and Fermat’s Last Theorem, in: Annals of Mathematics 141 (1995), S. 443–551.
• MacTutor History of Mathematics: Diophantus of Alexandria (englisch)
• Wikipedia: Diophantische Gleichung