Eine Lösung konstruieren

Lineare diophantische Gleichungen · Abschnitt 42 von 64

Checkliste

Bézout als Lösungsmaschine

$g=\operatorname{ggT}(a,b)$ mit Euklid bestimmen.
Rückwärts $au+bv=g$ darstellen.
Prüfen, dass $c=gk$ gilt.
Mit $k$ multiplizieren: $(x_0,y_0)=(uk,vk)$ .

Strategie

Alternativ eine Variable modulo eines Koeffizienten

Aus $ax+by=c$ folgt etwa $by\equiv c\pmod a$ . Ist $b$ modulo $a$ invertierbar, liefert dies schnell eine passende Restklasse für $y$ .

Typischer Fehler

Eine Lösung ist noch nicht die Lösungsmenge

Eine partikuläre Lösung beweist die Existenz, beantwortet aber nicht die Frage nach allen Lösungen. Dafür werden systematische Schrittweiten benötigt.

Gelöstes Beispiel

Beispiel mit 15, 21 und 6

Nach Division durch 3 entsteht $5x+7y=2$ . Das Paar $(-1,1)$ ist eine erste Lösung, denn $5(-1)+7(1)=2$ .