Diophantische Gleichungen

Von Alltagsproblemen sind Aufgaben folgender Art bekannt:

  • Beispiel 1: Für fünf Euro sollen zwei Sorten Kuchen zu 70 c t bzw. zu 90 c t gekauft werden.
  • Beispiel 2: Für zehn Euro sind Briefmarken zu 56 c t und 51 c t von der Post mitzubringen.
  • Beispiel 3: Kann man für 25 Euro Socken zu vier Euro und zu sechs Euro kaufen?

In allen Fällen kommen nur natürliche Zahlen als Lösungen infrage (falls das Problem überhaupt lösbar ist). Ein Rest darf nicht auftreten. Es sind somit spezielle lineare Gleichungen zu lösen.

  • Eine Gleichung der Form
    a x + b y = c ( )
    mit ganzzahligen Koeffizienten a, b und c, für die ganze Zahlen x und y als Lösungen gesucht sind, heißt eine (lineare) diophantische Gleichung in zwei Unbekannten.

Anmerkung: Entsprechend heißen Gleichungen der Form a 1 x 1 + a 2 x 2 + ... + a n x n = c diophantische Gleichungen mit n Unbekannten.

Die diophantische Gleichung ( ) lässt sich auch als lineare Kongruenz schreiben, denn aus a x = c b y = c + b g ergibt sich mit g = y :
a x c mod b ( )

Wir beweisen den folgenden Satz:

  • Die diophantische Gleichung ( ) bzw. die lineare Kongruenz ( ) ist genau dann lösbar, wenn der größte gemeinsame Teiler von a und b auch ein Teiler von c ist, wenn also gilt: g g T ( a , b ) = d ( m i t d | c )

Beweis:
(1) d = g g T ( a , b ) sei Teiler von c.
Der größte gemeinsame Teiler von a und b lässt sich stets als Linearkombination von a und b mit ganzen Zahlen u und v schreiben:
d = u a + v b
Die Voraussetzung d | c bedeutet, dass es eine ganze Zahl w gibt, mit c = d w . Multipliziert man obige Gleichung mit w, erhält man c = d w = ( w u ) a + ( w v ) b . . Somit sind x 0 = w u u n d y 0 = w v (spezielle) Lösungen der Gleichung ( ) .

(2) Sei umgekehrt die Gleichung ( ) lösbar mit x und y aus und d = g g T ( a , b ) .
Der größte gemeinsame Teiler d ist auch Teiler von jeder Linearkombination von a und b, also auch von a x + b y = c . Damit gilt d | c .

Das eingangs angegebene Beispiel 3 führt zur diophantischen Gleichung 4 x + 6 y = 25 . Da aber g g T ( 4, 6 ) = 2 ist und 2 kein Teiler von 25 ist, ist die Aufgabe nicht lösbar.

Für die weiteren Betrachtungen sei g g T ( a , b ) = 1 vorausgesetzt, da jede lösbare diophantische Gleichung nach Division durch d darauf zurückzuführen ist.
Ist das Paar ( x 0 ; y 0 ) eine spezielle Lösung von ( ) , so erhält man daraus die Gesamtheit aller Lösungen wie folgt:
x = x 0 + g b y = y 0 g a ( g )

Geht man von der zugehörigen linearen Kongruenz ( ) aus, so ergibt sich daraus die folgende Restklassengleichung mod b :
[ a ] [ x ] = [ c ] b z w . [ x ] = [ a ] 1 [ c ]

Wegen der Voraussetzung g g T ( a , b ) = 1 existiert das inverse Element zur Restklasse mod b .

Die Klasse [ x 0 ] = [ a ] 1 [ c ] ist eine Lösung der Restklassengleichung und damit auch der linearen Kongruenz. Alle Elemente x dieser Klasse haben die Form x = x 0 + g b ( m i t g ) .

Den zugehörigen Wert y als allgemeine Lösung von ( ) erhält man durch Einsetzen:
c = a x + b y = a ( x 0 + g b ) + b y = a x 0 + a g b + b y b y = c a x 0 a g b y = c a x 0 b a g
c a x 0 b ist die zu x 0 gehörende spezielle Lösung y 0 von ( ) , d.h. y = y 0 a g m i t g .

Lösungsmethoden

Jede lösbare diophantische Gleichung ( ) bzw. lineare Kongruenz ( ) besitzt eine unendliche Menge von Lösungspaaren. Zum Auffinden spezieller Lösungen gibt es verschiedene Methoden.

  1. Systematisches Probieren

Lösen durch systematisches Probieren bietet sich vor allem für den Fall an, dass die Zahlen a oder b „klein“ sind. Dann lassen sich in der linearen Kongruenz die Zahlen systematisch durch einen kleineren Repräsentanten ersetzen.

Wir betrachten dazu das oben gegebene Beispiel 1:

9 x + 62 y = 8 62 y 8 mod 9 b z w . 8 y 8 mod 9 a l s o y 0 = 1 9 x + 62 = 8 A l lg e m e i n e L ö s u n g : x 0 = 6 x = 6 + 62 g y = 1 9 g

  1. Methode der korrespondierenden Kongruenzen

Die Methode der korrespondierenden Kongruenzen verwendet mehrfach die Umwandlung von diophantischen Gleichungen in lineare Kongruenzen und umgekehrt, wobei jedes Mal nach dem kleineren Modul reduziert wird.

Am Beispiel 2 soll das Verfahren demonstriert werden:

51 x + 56 y = 1000 56 y 1000 mod 51 56 y 51 y ( 1000 19 51 ) mod 51 5 y 31 mod 51 5 y + 51 z = 31 51 z 31 mod 5 51 z 50 z ( 31 6 5 ) mod 5 z 1 mod 5 z = 1 + 5 g 5 y + 51 ( 1 + 5 g ) = 31 5 y = 20 255 g y = 4 51 g 51 x + 56 ( 4 51 g ) = 1000 51 x = 1224 + 51 56 g x = 24 + 56 g

Obwohl die diophantische Gleichung lösbar ist, gibt es keine Lösung für die vorgegebene Problemstellung, da für jedes g entweder x oder y negativ wird.

  1. Formale Bruchschreibweise

Beim Lösen mittels formaler Bruchschreibweise geht man von der linearen Kongruenz a x c mod b zu dem formalen Bruch x c a mod b über.Danach ersetzt man c oder a durch andere Repräsentanten mod b , bis man durch Kürzen zu einem ganzzahligen Wert gelangt.

Oben gegebenes Beispiel 1 wird mit dieser Methode gelöst:

   70 x + 90 y = 500
Wegen g g T ( 70, 90 ) = 10 u n d 10 | 500 ist die Gleichung lösbar und führt zu folgender der gekürzter Gleichung:
7 x + 9 y = 50 x 50 7 mod 9 50 5 mod 9 x 5 7 mod 9 7 25 mod 9 x 5 25 = 1 5 mod 9 1 10 mod 9 x 10 5 = 2 mod 9
Für y erhält man durch Einsetzen von x = 2 + 9 g in die diophantische Gleichung y = 4 7 g . Der Aufgabenstellung entsprechen die Werte x = 2 u n d y = 4.

  1. Euklidischer Algorithmus

Eine weitere Möglichkeit, diophantische Gleichungen lösen, ist das Lösen mithilfe des euklidischen Algorithmus.

Man bestimmt die Linearkombination von 1 = g g T ( a ; b ) und formt um, wie im nachfolgend wiederum am Beispiel 1 gezeigt wird:
7 x + 9 y = 50
Die Linearkombination des größten gemeinsamen Teilers 1 von 7 und 9 ergibt sich wie folgt:

9 = 1 7 + 2 u n d 7 = 3 2 + 1 1 = 7 3 2 = 7 3 ( 9 7 ) = 4 7 3 9
Multipliziert mit 50, so erhält man 50 = 200 7 150 9. Damit sind x 0 = 200 u n d y 0 = 150 spezielle Lösungen.
Die allgemeine Lösung ist gegeben durch:
x = 200 + 9 g y = 150 7 g
An diesem Beispiel erkennt man, dass beim euklidischen Algorithmus relativ große Zahlen als spezielle Lösungen auftreten können. Nur für g = 22 erhält man mit x = 2 u n d y = 4 eine Lösung, die der Aufgabenstellung genügt.

Weitere Lösungsverfahren gibt es unter Verwendung der eulerschen ϕ - F u n k t i o n und mithilfe von Kettenbrüchen.

Stand: 2010
Dieser Text befindet sich in redaktioneller Bearbeitung.

Lexikon Share
Lernprobleme in Mathe?
 

Mit deinem persönlichen Nachhilfe-Tutor Kim & Duden Learnattack checkst du alles. Jetzt 30 Tage risikofrei testen.

  • KI-Tutor Kim hilft bei allen schulischen Problemen
  • Individuelle, kindgerechte Förderung in Dialogform
  • Lernplattform für 9 Fächer ab der 4. Klasse
  • Über 40.000 Erklärvideos, Übungen & Klassenarbeiten
  • Rund um die Uhr für dich da

Einloggen