Das ggT-Lösbarkeitskriterium

Lineare diophantische Gleichungen · Abschnitt 5 von 64

Satz

Genau dann lösbar

Die Gleichung $ax+by=c$ ist eine Gerade – du suchst Gitterpunkte. Für ganze $a,b,c$ mit $(a,b)\ne(0,0)$ besitzt $ax+by=c$ genau dann eine ganzzahlige Lösung, wenn $\operatorname{ggT}(a,b)$ die Zahl $c$ teilt.

Beweis

Notwendigkeit und Hinreichendheit

Der ggT $g$ teilt jede Linearkombination $ax+by$ , also notwendig auch $c$ . Umgekehrt liefert Bézout ganze $u,v$ mit $au+bv=g$ ; bei $c=gk$ ist $(ku,kv)$ eine Lösung.

Gelöstes Beispiel

Sechs, neun und zwanzig

Da $\operatorname{ggT}(6,9)=3$ die Zahl 20 nicht teilt, ist $6x+9y=20$ über den ganzen Zahlen unlösbar.

Achtung

Ganzzahlig lösbar heißt noch nicht positiv lösbar

Das ggT-Kriterium entscheidet nur über ganzzahlige Lösungen. Ob positive oder nichtnegative Lösungen existieren, muss anschließend an der Parameterfamilie geprüft werden.