ベストアンサー
いつでもいくつかの小さな指数を計算して、余りの繰り返しパターンを見つけることができます。 。 2 ^ nの余りを18で割ってn = 1から計算してみましょう。
- n = 1、2 ^ 1 = 2、余りは2です;
- n = 2、2 ^ 2 = 4、余りは4;
- n = 3、2 ^ 3 = 8、余りは8;
- n = 4、2 ^ 4 = 16 、余りは16;
- n = 5、2 ^ 5 = 32、余りは14;
- n = 6、2 ^ 6 = 64、余りは10;
- n = 7、2 ^ 7 = 128、余りは2;
- n = 8、2 ^ 8 = 256、余りは4;
- \ cdots \ cdots
実際、指数が大きくなると、実際の2の累乗を計算する必要はありません。代わりに、前の余りに2を掛けて、その結果から新しい余りを見つけます。余りが6つの数字ごとに繰り返されることは明らかです。したがって、指数200の場合、200を6で割ったときの余りは2になります。したがって、2 ^ {200}を18で割ったときの余りは、2 ^ 2の余りと同じになります。 4.
回答
2 ^ 4 \ equiv -2 \ pmod {18}
\ implies(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 {したがって、4が余りです} \、2 ^ {200} \、\ text {を18で割ったとき}