Reduzieren und Lösungsklassen anheben

Lineare Kongruenzen systematisch lösen · Abschnitt 14 von 64

Strategie

Alle drei Zahlen teilen

Ist $g=\operatorname{ggT}(a,m)$ und $g\mid b$ , wird aus $ax\equiv b\pmod m$ die Kongruenz $(a/g)x\equiv b/g\pmod{m/g}$ . Entscheidend ist: Auch das Modul wird geteilt.

Gelöstes Beispiel

Von modulo 14 zu modulo 7

$6x\equiv8\pmod{14}$ reduziert sich zu $3x\equiv4\pmod7$ . Daraus folgt $x\equiv6\pmod7$ , also modulo 14 die zwei Klassen 6 und 13.

Formel

Klassen anheben

Aus $x\equiv x_0\pmod{m/g}$ entstehen modulo $m$ genau die Klassen $x\equiv x_0+k(m/g)$ für $k=0,1,\ldots,g-1$ .

Typischer Fehler

Das Modul nicht vergessen

Aus $6x\equiv8\pmod{14}$ darf nicht $3x\equiv4\pmod{14}$ gemacht werden. Korrekt ist nach Division durch 2 das neue Modul 7.