Zum Inhalt springen
Inhaltsverzeichnis öffnen
Kapitel 3Aufbau24 Min.

Modulare Division und Kürzen

Modulare Inverse · Abschnitt 11 von 64

Satz

Division bedeutet Multiplikation

Ist aa modulo mm invertierbar, darf axb(modm)ax\equiv b\pmod m mit a1a^{-1} multipliziert werden. Es folgt eindeutig xa1b(modm)x\equiv a^{-1}b\pmod m.

Gelöstes Beispiel

Sieben entfernen

Aus 7x5(mod26)7x\equiv5\pmod{26} und 71157^{-1}\equiv15 folgt x15523(mod26)x\equiv15\cdot5\equiv23\pmod{26}.

Satz

Sicheres Kürzen

Aus acbc(modm)ac\equiv bc\pmod m folgt bei ggT(c,m)=1\operatorname{ggT}(c,m)=1 die Kongruenz ab(modm)a\equiv b\pmod m. Man multipliziert mit c1c^{-1}.

Achtung

Noch keine Inverse, noch keine Division

Bei ggT(c,m)>1\operatorname{ggT}(c,m)>1 darf nicht modulo mm gekürzt werden. Wie eine solche Kongruenz mitsamt dem Modul korrekt reduziert wird, zeigt das nächste Kapitel.