Najlepsza odpowiedź
Zawsze możesz spróbować obliczyć kilka mniejszych wykładników i znaleźć powtarzający się wzór dla reszty . Obliczmy resztę z 2 ^ n podzieloną przez 18, zaczynając od n = 1:
- n = 1, 2 ^ 1 = 2, reszta to 2;
- n = 2, 2 ^ 2 = 4, reszta to 4;
- n = 3, 2 ^ 3 = 8, reszta to 8;
- n = 4, 2 ^ 4 = 16 , reszta to 16;
- n = 5, 2 ^ 5 = 32, reszta to 14;
- n = 6, 2 ^ 6 = 64, reszta to 10;
- n = 7, 2 ^ 7 = 128, reszta to 2;
- n = 8, 2 ^ 8 = 256, reszta to 4;
- \ cdots \ cdots
W rzeczywistości, gdy wykładniki stają się większe, nie trzeba obliczać rzeczywistej potęgi 2; zamiast tego po prostu pomnóż poprzednią resztę przez 2, a następnie znajdź nową resztę z tego wyniku. Oczywiste jest, że pozostałe powtarzają się co 6 liczb. Tak więc dla wykładnika 200 po prostu znajdujemy resztę z dzielenia 200 przez 6, co daje 2. Zatem reszta z dzielenia 2 ^ {200} przez 18 jest taka sama, jak reszta z 2 ^ 2, co równa się 4.
Odpowiedź
2 ^ 4 \ equiv -2 \ pmod {18}
\ implikuje (2 ^ 4) ^ 5 \ equiv (-2 ) ^ 5 \ pmod {18}
\ implies (2 ^ 4) ^ 5 \ equiv -32 \ pmod {18}
\ implies 2 ^ {20} \ equiv 4 \ pmod {18}
\ implies (2 ^ {20}) ^ 5 \ equiv 4 ^ 5 \ pmod {18}
\ implies (2 ^ {100}) \ equiv 1024 \ pmod {18}
\ implies (2 ^ {100}) \ equiv -2 \ pmod {18}
\ implies (2 ^ {200}) \ equiv (-2) ^ 2 \ pmod {18}
\ implies (2 ^ {200}) \ equiv 4 \ pmod {18}
\ text {Stąd 4 to reszta kiedy} \, 2 ^ {200} \, \ text {jest podzielone przez 18}