Das ggT-Lösbarkeitskriterium

Lineare Kongruenzen systematisch lösen · Abschnitt 13 von 64

Intuition

Eine versteckte ganzzahlige Gleichung

Die Gleichung $axequiv bpmod m$ sucht Restklassen für $x$ . Manchmal gibt es eine, manchmal mehrere, manchmal keine – der ggT entscheidet.

Satz

Lösbarkeitskriterium

Die Kongruenz $ax\equiv b\pmod m$ ist genau dann lösbar, wenn $g=\operatorname{ggT}(a,m)$ die Zahl $b$ teilt. Im lösbaren Fall gibt es genau $g$ Klassen modulo $m$ .

Beweis

Warum das Kriterium gilt

Jede Zahl $ax-my$ ist durch $g$ teilbar, also muss $g\mid b$ gelten. Umgekehrt liefert Bézout $ua+vm=g$ . Für $b=gc$ folgt $a(uc)+m(vc)=b$ und damit eine Lösung.

Gelöstes Beispiel

Existenz vor Rechnung

Für $6x\equiv8\pmod{14}$ ist $g=2$ und $2\mid8$ : Es gibt Lösungen. Für $6x\equiv5\pmod{14}$ gilt $2\nmid5$ : Die Kongruenz ist unlösbar.