Citat:
Ursprungligen postat av
DenSvartaBollen
är det sant att skriva följande?
59^1869=59^9=(59^2)^4*(59)==(4^4)*59 mod 19 ?
dvs bryta ner till problemet att hitta resten av 4^4 * 59 när det delas med 19?
Den första ekvivalensen gäller inte, men övriga är korrekta.
Om a = A (mod n) och b = B (mod n) så gäller
a+b = A+B (mod n),
a*b = A*B (mod n),
a^k = A^k (mod n) för k = 0, 1, 2, 3, ...
I det aktuella fallet skulle jag välja dessa ekvivalenser:
59 = 3*19 + 2 = 2 (mod 19)
Enligt Fermats lilla sats gäller sedan 2^18 = 1 (mod 19), så
59^1869 = 2^1869 = (2^18)^103 * 2^15 = 2^15 = 32768 = 12 (mod 19)