Gleichungen mit ausschließlich ganzzahligen Lösungen nennt man diophantisch, wobei sie im linearen Fall (für zwei Variablen) die folgende Form haben:
| (4.10) |
Solche Gleichungen haben genau dann eine Lösung, wenn der größte gemeinsame Teiler den Wert teilt. Im Zusammenhang mit EUKLID’s Algorithmus wurde dies praktisch schon nachgewiesen – auch daß es unendlich viele solcher Lösungen gibt, kam in Abschnitt 4.1.1 zur Sprache.
Zuerst bemerken wir, daß die Differenz zweier Lösungen und die homogene Gleichung erfüllt.
Mit und läßt sich sogar schreiben
und es liegen die Lösungen , auf der Hand (Einsetzen ergibt ).52 Findet man jetzt noch eine partikuläre Lösung , dann ergeben sich alle weiteren zu:
Partikuläre Lösungen für haben wir aber schon mittels der erweiterten GCD-Algorithmen zur Verfügung, denn mit der BéZOUT’s Identität (den Index jetzt weggelassen)
gilt:
Eine partikuläre Lösung (, ) kann deshalb mit Hilfe der BéZOUT-Kofaktoren gegeben werden.
Die Vielfalt aller Lösungen stellt sich dadurch wiefolgt dar:
Für den Spezialfall entartet die Formel zu: