Lineare diophantische Gleichungen mit zwei Veränderlichen.


Diophantische Gleichung mit zwei Veränderlichen aussieht:

wo — gegebene ganze Zahlen sind, und — unbekannte ganze Zahlen sind.
Unten betrachtet man ein paar klassische Aufgaben zu diesen Gleichungen: Ermittlung der beliebigen Auflösung, Erhaltung aller Auflösungen, Ermittlung von der Anzahl der Auflösungen und die Auflösungen selbst im bestimmten Abschnitt, Ermittlung der Auflösung mit der kleinsten Summe der Unbekannten.

Entarteter Fall


Ein entarteter Fall schließen wir gleich aus der Betrachtung: wenn . In diesem Fall ist es klar, dass die Gleichung entweder unendlich viele beliebiger Auflösungen hat, oder hat keine Auflösungen überhaupt(das hängt davon ab, ob oder nicht).

Ermittlung einer Auflösung


Die Auflösung einer diophantischen Gleichung zu finden kann man mithilfe des erweiterten Euklidisches Algorithmus.
Der erweiterte Euklidischer Algoritmus findet nach den Gegebenen a und b ihren größten gemeinsamen Teiler
, und auch solche Koeffiziente und , dass:


Es wird behauptet, dass wenn C wird durch geteilt, dann hat die diophantische Gleichung die Auflösung;sonst hat die diophantische Gleichung keine Auflösungen. Die Beweisung geht aus dem offensichtlichen Fakt, dass die lineare Kombination von zwei Zahlen nach wie vor durch ihren gemeinsamen Teiler geteilt werden muss.
Vermuten wir, dass C wird durch geteilt, dann erfüllt , ...


d.h. eine der Auflösungen der diophantischen Gleichung sind die Zahlen:


Erhaltung aller Auflösungen


Wir zeigen, wie man alle anderen Auflösungen (es gibt sehr sehr viel) der diophantischen Gleichung erhalten kann, wenn man um eine von der Auflösungen weißt .
also, sai es , und die Zahlen genügen die Bedingung:

Dann bemerken wir,dass wenn wir zu die Zahl addieren und gleichzeitig von , abziehen, wir verletzen die Gleichheit nicht:

Es ist offensichtlich, dass man dieses Prozess mehrmals wiederholen kann, d.h. alle Zahlen der Form:

sind die Auflösungen einer diophantischen Gleichung.
Noch mehr, nur die Zahlen solcher Form sind die Auflösungen, d.h wir haben die Mehrheit aller Auflösungen der diophantischen Gleichung beschrieben (sie ist unendlich, wenn es keine zusätzliche Bedingungen gibt).