Berechnen Sie zu 308 das multiplikative Inverse modulo 585.
Alternativer Lösungsweg: Wegen 585=5*9*13
Suchst du diejenigen Zahlen x, für die gilt:
308 x ≡ 1 mod 5 (Kürzer: 3 x ≡ 1 mod 5)
und
308 x ≡ 1 mod 9 (Kürzer: 2 x ≡ 1 mod 9)
und
308 x ≡ 1 mod 13 (Kürzer: 9 x ≡ 1 mod 13)
Die letzte Kongruenz wird erfüllt für x=3, also gilt x=13k+3.
Einsetzen in
2 x ≡ 1 mod 9
ergibt
26k+6 ≡ 1 mod 9
26k+5 ≡ 0 mod 9
-k+5 ≡ 0 mod 9
k ≡ 5 mod 9
k=9n+5
Mit x=13k+3 wird daraus
x=117n+68
Das kann man dann in der ersten Kongruenz verwenden.
