Beste svaret
Du kan alltid prøve å beregne noen få mindre eksponenter og finne et gjentakende mønster for resten . La oss beregne resten av 2 ^ n delt på 18, og begynne med n = 1:
- n = 1, 2 ^ 1 = 2, resten er 2;
- n = 2, 2 ^ 2 = 4, resten er 4;
- n = 3, 2 ^ 3 = 8, resten er 8;
- n = 4, 2 ^ 4 = 16 , resten er 16;
- n = 5, 2 ^ 5 = 32, resten er 14;
- n = 6, 2 ^ 6 = 64, resten er 10;
- n = 7, 2 ^ 7 = 128, resten er 2;
- n = 8, 2 ^ 8 = 256, resten er 4;
- \ cdots \ cdots
Når eksponentene blir større, trenger du faktisk ikke å beregne de faktiske kreftene på 2; i stedet multipliserer du bare den forrige resten med 2, og finner deretter den nye resten fra det resultatet. Det er klart at resten gjentar hvert sjette tall. Så for eksponenten 200 finner vi bare ut resten når 200 er delt med 6, som er 2. Derfor er resten når 2 ^ {200} er delt med 18 det samme som resten for 2 ^ 2, som tilsvarer 4.
Svar
2 ^ 4 \ equiv -2 \ pmod {18}
\ innebærer (2 ^ 4) ^ 5 \ equiv (-2 ) ^ 5 \ pmod {18}
\ innebærer (2 ^ 4) ^ 5 \ equiv -32 \ pmod {18}
\ innebærer 2 ^ {20} \ equiv 4 \ pmod {18}
\ innebærer (2 ^ {20}) ^ 5 \ equiv 4 ^ 5 \ pmod {18}
\ innebærer (2 ^ {100}) \ equiv 1024 \ pmod {18}
\ impliserer (2 ^ {100}) \ equiv -2 \ pmod {18}
\ impliserer (2 ^ {200}) \ equiv (-2) ^ 2 \ pmod {18}
\ innebærer (2 ^ {200}) \ equiv 4 \ pmod {18}
\ text {Derfor er 4 resten når} \, 2 ^ {200} \, \ text {er delt med 18}