Tagchen
a) [10*((10^12)^12)] = 10 mod 21
10 = 10 mod 21
((10^12)^12) = 1 mod 21
Wenn man nun also die fettgedruckten Reste miteinander multipliziert:
10*1=10 bekommt man genau den Rest von a wieder.
Warum ist das so? bzw warum funktioniert das?
Hallo Unbekannter,
stell dir vor du hast zwei ganze Zahlen a1 und a 2 und es gilt
a1 ≡ r1 mod n und
a2 ≡ r2 mod n
Das bedeutet es gibt zwei ganze Zahlen k1 und k2 so dass gilt
a1=k1n+r1 und
a2=k2n+r2
Dann folgt für das Produkt
a1a2=k1k2n2+(k1r2+k2r1)n+r1r2 ≡ r1r2 mod n
Gruß
hendrik