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 ax≡b(modm)ax\equiv b\pmod m mit a−1a^{-1} multipliziert werden. Es folgt eindeutig x≡a−1b(modm)x\equiv a^{-1}b\pmod m.

Gelöstes Beispiel

Sieben entfernen

Aus 7x≡5(mod26)7x\equiv5\pmod{26} und 7−1≡157^{-1}\equiv15 folgt x≡15⋅5≡23(mod26)x\equiv15\cdot5\equiv23\pmod{26}.

Satz

Sicheres Kürzen

Aus ac≡bc(modm)ac\equiv bc\pmod m folgt bei ggT⁡(c,m)=1\operatorname{ggT}(c,m)=1 die Kongruenz a≡b(modm)a\equiv b\pmod m. Man multipliziert mit c−1c^{-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.