Der Schnitt von Restklassen

Kongruenzsysteme · Abschnitt 33 von 64

Intuition

Zwei Zahlenspuren

Mehrere Kongruenzen gleichzeitig: Du suchst Zahlen, die in mehreren Restfächern zugleich liegen. Manchmal passt alles, manchmal widerspricht sich das System.

Definition

Simultane Kongruenzen

Ein ganzes $x$ löst ein Kongruenzsystem, wenn es jede angegebene Kongruenz gleichzeitig erfüllt. Ein einzelner Treffer genügt noch nicht als vollständige Lösungsangabe.

Gelöstes Beispiel

Reste zwei und drei

Aus $x\equiv2\pmod3$ folgt $x=2+3k$ . Einsetzen in $x\equiv3\pmod5$ liefert $k\equiv2\pmod5$ und schließlich $x\equiv8\pmod{15}$ .

Achtung

Das Produkt ist nicht immer das Endmodul

Nur bei teilerfremden Modulen gilt $\operatorname{kgV}(m,n)=mn$ . Allgemein wiederholen sich gemeinsame Lösungen modulo des kgV.