Lineare diophantische Gleichungen

4.2 Lineare diophantische Gleichungen

Gleichungen mit ausschließlich ganzzahligen Lösungen $x,y,...∈ ℤ$ nennt man diophantisch, wobei sie im linearen Fall (für zwei Variablen) die folgende Form haben:

ax+ by = c, mit a,b,c∈ ℕ.

(4.10)

Solche Gleichungen haben genau dann eine Lösung, wenn der größte gemeinsame Teiler $d = gcd(a,b)$ den Wert $c$ 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 $(x1,y1)$ und $(x2,y2)$ die homogene Gleichung $ax + by= 0$ erfüllt.

Mit $-- a= d a$ und $-- b= d b$ läßt sich sogar schreiben

-- -- ax+ by= 0

und es liegen die Lösungen $-- -- (x,y) = (n b,− na)$ , $n ∈ℤ$ auf der Hand (Einsetzen ergibt $-- -- -- ax +by = anb− bna-= 0$ ).⁵² Findet man jetzt noch eine partikuläre Lösung $(x2,y2)$ , dann ergeben sich alle weiteren zu:

Partikuläre Lösungen $(x2,y2)$ für $ax2+ by2 = c$ haben wir aber schon mittels der erweiterten GCD-Algorithmen zur Verfügung, denn mit der BéZOUT’s Identität (den Index $2$ jetzt weggelassen)

gilt:

- - - ax + by= c= dc= α ca+ βcb.

Eine partikuläre Lösung ( $∧ x2= x$ , $∧ y2= y$ ) kann deshalb mit Hilfe der BéZOUT-Kofaktoren $α,β$ gegeben werden.

Die Vielfalt aller Lösungen stellt sich dadurch wiefolgt dar:

Für den Spezialfall $d = gcd(a,b)= 1$ entartet die Formel zu: