Alle Lösungen und Schranken

Lineare diophantische Gleichungen · Abschnitt 7 von 64

Gelöstes Beispiel

Die vollständige Familie

Ist $(x_0,y_0)$ eine Lösung und $g=\operatorname{ggT}(a,b)$ , so lauten alle Lösungen $x=x_0+(b/g)t$ und $y=y_0-(a/g)t$ mit $t\in\mathbb Z$ .

Beweis

Differenzen zweier Lösungen

Die Differenz zweier Lösungen erfüllt $a\Delta x+b\Delta y=0$ . Nach Division durch $g$ und Euklids Lemma muss $b/g$ die Änderung von $x$ und $a/g$ die entgegengesetzte Änderung von $y$ teilen.

Strategie

Nebenbedingungen werden Intervallgrenzen

Setze die Parameterform in $x\ge0$ , $y\ge0$ oder gegebene Obergrenzen ein. Der ganzzahlige Parameter $t$ liegt danach in einem expliziten Intervall.

Checkliste

Vollständige Antwort

ggT-Kriterium geprüft?
Eine partikuläre Lösung verifiziert?
Schrittweiten durch $g$ geteilt?
Gegenläufige Vorzeichen verwendet?
Parameterbereich aus allen Nebenbedingungen bestimmt?