Beste antwoord
Eerst moeten we kijken naar de modulus (of de nummer dat we proberen te delen door). In dit geval is dat 1818. Vervolgens voegt u 1818 in in de totient-functie van Euler om ϕ (18) ϕ (18). In het bijzonder geldt voor alle gehele getallen nn
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
waar het product alle unieke priemfactoren van nn doorloopt. Dus in dit geval
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Oké, dus de volgende stap is de stelling van Euler , die zegt dat voor elk ander geheel getal aa relatief priem tot nn, we hebben dat aa tot de ϕ (n) ϕ (n) macht een rest van 11 overlaat wanneer gedeeld door nn. Dat wil zeggen,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Aangezien 1717 inderdaad relatief priem is tot 1818, weten we 176176 bladeren een herinnering van 1. Dit betekent dat we 176176 van 1720017200 gewoon kunnen blijven delen zonder de rest te wijzigen. Een andere manier om dit te zeggen is dat 17 op elke macht die “een veelvoud van 6 is, een rest van 1 overhoudt. Dus uiteindelijk, aangezien 200 2 meer is dan een veelvoud van 6, weten we dat
17200≡172 (mod18) .17200≡172 (mod18).
Dit maakt het probleem een stuk eenvoudiger – we zijn er bijna! Een snelkoppeling hier om het probleem te beëindigen, is te beseffen dat 1717 een rest van −1−1 overlaat wanneer gedeeld door 1818 (dat wil zeggen 17≡ − 1 (mod18) 17≡ − 1 (mod18)), dus 172172 laat een rest van (- 1) 2 = 1. (- 1) 2 = 1.
Ons antwoord is dus 1 . De volgende keer heeft u een probleem met de rest van een groot vermogen, kunt u deze mooie algemene oplossing gebruiken en tegelijkertijd slim klinken :). Als je “de modmod-notatie nog niet eerder hebt gezien, zie dan Modulaire rekenkunde .
PS Je hebt misschien wel eens gehoord van een speciaal geval van deze stelling genaamd Fermats kleine stelling , die werkt als je een modulus hebt die “een priemgetal is (niet het geval hier). De stelling zegt dat voor elk priemgetal pp en geheel getal aa dat geen veelvoud is van pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Dit is een interessante truc, maar het is in wezen hetzelfde als wat “hierboven is, aangezien ϕ (p) = p − 1ϕ (p) = p − 1 voor elke priempp. Dit soort vragen wordt heel eenvoudig als je het concept van negatieve resten . Probeer altijd het dividend te verlagen tot 1 of -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Antwoord
Belangrijke achtergrond die nodig is om het probleem op te lossen :
We weten dat de rest die wordt verkregen als r pq deelt, een product is van restanten die zijn verkregen als r p en q afzonderlijk deelt. Op restanten wordt dit lemma genoemd. U kunt het bewijzen met de divisiestelling van Euclid.
De oplossing
17 wanneer gedeeld door 18 resterende bladeren -1 (het is handig om met -1 te werken dan met 17)
Door het restlemma toe te passen op 17 × 17 × 17 … × 17 (2000 keer) wanneer gedeeld door 18, wordt rest verkregen wanneer de individuele resten worden vermenigvuldigd, dwz -1 × -1 .. × -1 (2000 keer) dat is rest is 1 \ blacksquare
Als het 17 was verhoogd tot een oneven getal, zou de rest -1 of 17 zijn .