Eine Lösung von http://www.arndt-bruenner.de/mathe/scripts/diophant.htm
Es soll die diophantische Gleichung 217x + 63y = 10 gelöst werden.
Das von Euler entwickelte Verfahren ist eng verwandt mit dem euklidischen Algorithmus.
Man betrachtet nur die jeweiligen Reste bei der Division durch einen der Koeffizienten,
geeigneterweise den mit dem kleinsten Betrag, und reduziert die Reste dadurch solange,
bis nur noch ein ganzzahliger Rest bleibt.
Die Variable mit dem kleinsten Koeffizienten ist y. Die Gleichung wird nach y umgeformt:
63y = 10 - 217x
10 - 217x
y = ———————————
63
Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:
10 - 28x
y = -3x + ——————————
63
Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter a wird eingeführt und dem Bruch gleichgesetzt:
10 - 28x
a = ——————————
63
63a = 10 - 28x
Die Variable mit dem kleinsten Koeffizienten ist x. Die Gleichung wird nach x umgeformt:
28x = 10 - 63a
10 - 63a
x = ——————————
28
Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:
10 - 7a
x = -2a + —————————
28
Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter b wird eingeführt und dem Bruch gleichgesetzt:
10 - 7a
b = —————————
28
28b = 10 - 7a
Die Variable mit dem kleinsten Koeffizienten ist a. Die Gleichung wird nach a umgeformt:
7a = 10 - 28b
10 - 28b
a = ——————————
7
Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:
3
a = 1 - 4b + ———
7
Der Bruch ist definitiv nicht ganzzahlig.
===> Es existiert keine ganzzahlige Lösung!
___________________________________________________________________________________________
Javascript von Arndt Brünner
