Beste antwoord
Je kunt altijd proberen een paar kleinere exponenten te berekenen en een herhalend patroon te vinden voor de restanten . Laten we de rest van 2 ^ n gedeeld door 18 berekenen, beginnend met n = 1:
- n = 1, 2 ^ 1 = 2, rest is 2;
- n = 2, 2 ^ 2 = 4, rest is 4;
- n = 3, 2 ^ 3 = 8, rest is 8;
- n = 4, 2 ^ 4 = 16 , rest is 16;
- n = 5, 2 ^ 5 = 32, rest is 14;
- n = 6, 2 ^ 6 = 64, rest is 10;
- n = 7, 2 ^ 7 = 128, rest is 2;
- n = 8, 2 ^ 8 = 256, rest is 4;
- \ cdots \ cdots
In feite, als de exponenten groter worden, hoeft u de werkelijke machten van 2 niet te berekenen; in plaats daarvan vermenigvuldig je gewoon de vorige rest met 2 en vind je de nieuwe rest uit dat resultaat. Het is duidelijk dat de restanten elke 6 cijfers herhalen. Dus voor de exponent 200, vinden we gewoon de rest wanneer 200 wordt gedeeld door 6, wat 2 is. Daarom is de rest wanneer 2 ^ {200} gedeeld door 18 is hetzelfde als de rest voor 2 ^ 2, wat gelijk is aan 4.
Antwoord
2 ^ 4 \ equiv -2 \ pmod {18}
\ impliceert (2 ^ 4) ^ 5 \ equiv (-2 ) ^ 5 \ pmod {18}
\ impliceert (2 ^ 4) ^ 5 \ equiv -32 \ pmod {18}
\ impliceert 2 ^ {20} \ equiv 4 \ pmod {18}
\ impliceert (2 ^ {20}) ^ 5 \ equiv 4 ^ 5 \ pmod {18}
\ impliceert (2 ^ {100}) \ equiv 1024 \ pmod {18}
\ impliceert (2 ^ {100}) \ equiv -2 \ pmod {18}
\ impliceert (2 ^ {200}) \ equiv (-2) ^ 2 \ pmod {18}
\ impliceert (2 ^ {200}) \ equiv 4 \ pmod {18}
\ text {4 is dus de rest wanneer} \, 2 ^ {200} \, \ text {wordt gedeeld door 18}