Prev    Up    Next  

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.

pict

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  ).52 Findet man jetzt noch eine partikuläre Lösung (x2,y2)  , dann ergeben sich alle weiteren zu:

pict

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)

pict

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.

pict

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

pict

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

pict