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

シェアする

スポンサーリンク

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

2100を2016で割った余りを求める。

スポンサーリンク

合同式で解く

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

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

2100は32、つまり25で割り切れるのは明らかだから、合同式で表すと、

2100 ≡ 0 (mod 32) ……①

次に、2100を63で割った余りを求める。

26(= 64)を63で割った余りは1だから、

26 ≡ 1 (mod 63)

2100 ≡ (26)16 × 24 ≡ 116 × 16 ≡ 16

よって、

2100 ≡ 16 (mod 63) ………②

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

2016で割った余り

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

①×63と②×32より、

63 × 2100 ≡ 0 (mod 2016) ……③

32 × 2100 ≡ 512 (mod 2016) ……④

④×2より、

64 × 2100 ≡ 1024 (mod 2016) ……⑤

⑤-③より、

2100 ≡ 1024 (mod 2016)

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

補足

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

32 × 2100 ≡ 512 (mod 2016) 

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

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

2100 = 63a + 16 (aは正の整数)

を意味している。

両辺を32倍すると、

32 × 2100 = 32(63a + 16) = 2016a + 512

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

32 × 2100 ≡ 512 (mod 2016) 

となる。

スポンサーリンク

シェアする

twitterをフォローする
twitterをフォローする

ブログを購読する
ブログを購読する

follow us in feedly RSS