【合同式】2の100乗を2016で割った余り（早稲田大学）

YouTubeで次のような早稲田大学の入試問題を見つけた。

2¹⁰⁰を2016で割った余りを求める。

合同式で解く

わたしは次のように合同式を使って解いてみた。

2016という数字は大きいので、「2016=32×63」より、32と63で割って考えてみる。

2¹⁰⁰は32、つまり2⁵で割り切れるのは明らかだから、合同式で表すと、

2¹⁰⁰ ≡ 0 (mod 32)　……①

次に、2¹⁰⁰を63で割った余りを求める。

2⁶（= 64）を63で割った余りは1だから、

2⁶ ≡ 1 (mod 63)

2¹⁰⁰ ≡ (2⁶)¹⁶ × 2⁴ ≡ 1¹⁶ × 16 ≡ 16

よって、

2¹⁰⁰ ≡ 16 (mod 63)　………②

上記の①②の2つの式から答えを求める。

2016で割った余り

①②を2016で割った式にそろえる。

①×63と②×32より、

63 × 2¹⁰⁰ ≡ 0 (mod 2016)　……③

32 × 2¹⁰⁰ ≡ 512 (mod 2016)　……④

④×2より、

64 × 2¹⁰⁰ ≡ 1024 (mod 2016)　……⑤

⑤-③より、

2¹⁰⁰ ≡ 1024 (mod 2016)

よって、答えは1024となる。

補足

なぜ、「2¹⁰⁰ ≡ 16 (mod 63)」の両辺を32倍すると、

32 × 2¹⁰⁰ ≡ 512 (mod 2016)　

となるのか、補足説明する。

「2¹⁰⁰ ≡ 16 (mod 63)」という合同式は、

2¹⁰⁰ = 63a + 16 （aは正の整数）

を意味している。

両辺を32倍すると、

32 × 2¹⁰⁰ = 32(63a + 16) = 2016a + 512

となり、「32 × 2¹⁰⁰を2016で割った余りは512」を意味するから、合同式で表すと、

32 × 2¹⁰⁰ ≡ 512 (mod 2016)　

となる。