Citat:
Ursprungligen postat av
MrHolst
Vad blir resten när
123^456 delas med 100
123^459==23^456(mod100)
Sen vet ifan hur jag ska gå vidare
har testat 23^2=529==29(mod100) så det gör varken bu eller bä
Om du känner till kinesiska restsatsen så kan man göra så här. (Samt Eulers sats vilken jag kommer använd då jag säger att 2^20 = 1 (mod 25)).
Låt f(n) vara en kanoniska projektionen från Z_100 till Z_4 * Z_25. Nu söker vi f^(-1), detta gör vi genom att identifiera vilka 0 <= a, b < 100 som ger att f(a) = (1, 0) och f(b) = (0, 1). Detta gör man lättast genom att gissa sig fram. Så gissning ger att a = 25 och b = 76. Nu beräknar vi
123^456 = 3^456 = (-1)^456 = 1 (mod 4)
och
123^456 = (-2)^456 = 2^456 = 2^(20*22 + 16) = 2^16 = 256^2 = 6^2 = 36 = 11 (mod 25)
Nu använder vi att
f^(-1)(1, 11) = f^(-1)(1, 0) + 11*f^(-1)(0, 1) = 25 +11*76 = 25 + 836 = 861 = 61 (mod 100).