Alle Lösungen und zusätzliche Schranken

Lineare diophantische Gleichungen · Abschnitt 43 von 64

Satz

Die vollständige Lösungsfamilie

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

Gelöstes Beispiel

Fortsetzung des Beispiels

Für $15x+21y=6$ und $(-1,1)$ lauten alle Lösungen $x=-1+7t$ und $y=1-5t$ . Die Änderungen tragen $15\cdot7+21\cdot(-5)=0$ bei.

Beweis

Warum fehlen keine Lösungen?

Die Differenz zweier Lösungen erfüllt $a\Delta x+b\Delta y=0$ . Nach Division durch den ggT sind $a/g$ und $b/g$ teilerfremd; daraus folgen $b/g\mid\Delta x$ und $a/g\mid\Delta y$ . Genau dies erzeugt die angegebene Parameterform.

Strategie

Positivität wird zu einer Schranke für t

Setze die Parameterform in Bedingungen wie $x\ge0$ und $y\ge0$ ein. Zwei lineare Ungleichungen begrenzen den ganzzahligen Parameter meist auf ein kurzes Intervall.