Beste Antwort
Sie können immer versuchen, einige kleinere Exponenten zu berechnen und ein sich wiederholendes Muster für die verbleibenden zu finden . Berechnen wir den Rest von 2 ^ n geteilt durch 18, beginnend mit n = 1:
- n = 1, 2 ^ 1 = 2, Rest ist 2;
- n = 2, 2 ^ 2 = 4, Rest ist 4;
- n = 3, 2 ^ 3 = 8, Rest ist 8;
- n = 4, 2 ^ 4 = 16 , der Rest ist 16;
- n = 5, 2 ^ 5 = 32, der Rest ist 14;
- n = 6, 2 ^ 6 = 64, der Rest ist 10;
- n = 7, 2 ^ 7 = 128, Rest ist 2;
- n = 8, 2 ^ 8 = 256, Rest ist 4;
- \ cdots \ cdots
Wenn die Exponenten größer werden, müssen Sie die tatsächlichen Potenzen von 2 nicht berechnen. Stattdessen multiplizieren Sie einfach den vorherigen Rest mit 2 und suchen dann den neuen Rest aus diesem Ergebnis. Es ist klar, dass die Reste alle 6 Zahlen wiederholen. Für den Exponenten 200 finden wir also nur den Rest heraus, wenn 200 durch 6 geteilt wird, was 2 ist. Daher ist der Rest, wenn 2 ^ {200} durch 18 geteilt wird, der gleiche wie der Rest für 2 ^ 2, der gleich ist 4.
Antwort
2 ^ 4 \ equiv -2 \ pmod {18}
\ impliziert (2 ^ 4) ^ 5 \ equiv (-2 ) ^ 5 \ pmod {18}
\ impliziert (2 ^ 4) ^ 5 \ equiv -32 \ pmod {18}
\ impliziert 2 ^ {20} \ equiv 4 \ pmod {18}
\ impliziert (2 ^ {20}) ^ 5 \ equiv 4 ^ 5 \ pmod {18}
\ impliziert (2 ^ {100}) \ Äquiv. 1024 \ pmod {18}
\ impliziert (2 ^ {100}) \ Äquiv. -2 \ pmod {18}
\ impliziert (2 ^ {200}) \ Äquiv (-2) ^ 2 \ pmod {18}
\ impliziert (2 ^ {200}) \ equiv 4 \ pmod {18}
\ text {Daher ist 4 der Rest wenn} \, 2 ^ {200} \, \ text {durch 18}
geteilt wird