Das Verträglichkeitskriterium

Kongruenzsysteme · Abschnitt 34 von 64

Satz

Allgemeines Verträglichkeitskriterium

Das System $x\equiv a\pmod m$ , $x\equiv b\pmod n$ ist genau dann lösbar, wenn $a\equiv b\pmod{\operatorname{ggT}(m,n)}$ .

Beweis

Differenz und lineare Kongruenz

Eine gemeinsame Lösung erzwingt $a-b=ns-mr$ , also die Teilbarkeit durch den ggT. Umgekehrt ist bei dieser Teilbarkeit $mk\equiv b-a\pmod n$ lösbar; dann erfüllt $x=a+mk$ beide Bedingungen.

Gelöstes Beispiel

Kompatibel oder nicht?

Die Reste 1 modulo 4 und 3 modulo 6 stimmen modulo 2 überein: lösbar. Die Reste 1 modulo 4 und 2 modulo 6 stimmen modulo 2 nicht überein: unlösbar.

Checkliste

Existenz vor Konstruktion

Module und Reste sauber notieren.
ggT der Module bestimmen.
Restdifferenz bilden.
Teilbarkeit prüfen.
Erst dann eine Lösung konstruieren.