Beste svaret
Først må vi se på modulen (eller nummeret vi prøver å dele på). I dette tilfellet er det 1818. Deretter setter du inn 1818 i Eulers totient-funksjon for å få ϕ (18) ϕ (18). Spesielt for alle heltall nn har vi
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
der produktet går over alle unike hovedfaktorer for nn. Så i dette tilfellet,
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, så neste trinn er Eulers teorem , som sier at for ethvert annet heltall aa som er relativt prime til nn, har vi at aa til ϕ (n) ϕ (n) kraften etterlater en rest på 11 når delt på nn. Det vil si
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Siden 1717 faktisk er relativt prime til 1818, vet vi 176176 blader en påminnelse om 1. Dette betyr at vi bare kan dele 176176 ut av 1720017200 uten å endre resten. En annen måte å si dette på er at 17 til enhver kraft som «er et multiplum av 6, vil gi en rest på 1. Så til slutt, siden 200 er 2 mer enn et multiplum av 6, vet vi at
17200≡172 (mod18) .17200≡172 (mod18).
Dette gjør problemet mye enklere – vi er nesten der! En snarvei her for å fullføre problemet er å innse at 1717 etterlater en rest av −1−1 delt på 1818 (dvs. 17≡ − 1 (mod18) 17≡ − 1 (mod18)), så 172172 etterlater en rest av (- 1) 2 = 1. (- 1) 2 = 1.
Så vårt svar er 1 . Neste gang du har et problem som involverer resten med stor kraft, kan du bruke denne fine generaliserte løsningen og høres smart samtidig ut :). Hvis du ikke har sett modmod-notasjonen før, se Modular arithmetic .
PS Du har kanskje hørt om et spesielt tilfelle av denne teoremet kalt Fermat «lille setning , som fungerer når du har en modul som» er primtall (ikke tilfelle her). Teoremet sier at for alle primer og heltall aa som ikke er et multiplum av pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Dette er et interessant triks, men det er i utgangspunktet det samme som det som står ovenfor siden ϕ (p) = p − 1ϕ (p) = p − 1 for enhver primærside. Denne typen spørsmål blir veldig enkle hvis du forstår begrepet negative rester . Forsøk alltid å redusere utbyttet til 1 eller -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Svar
Viktig bakgrunn som trengs for å løse problemet :
Vi vet at resten oppnådd når r deler pq er et produkt av rester oppnådd når r deler p og q separat. Dette kalles lemma på resten. Du kan bevise det ved Euclids divisjonssetning.
Løsningen
17 når den deles med 18 forlater resten -1 (det er praktisk å jobbe med -1 enn 17)
Å bruke resten lemma på 17 × 17 × 17 … × 17 (2000 ganger) delt på 18 vil bli oppnådd når individuelle rester multipliseres, dvs. -1 × -1 .. × -1 (2000 ganger) som er resten er 1 \ svart kvadrat
Hvis det var 17 hevet til et oddetall, ville resten være -1 eller 17 .