2の100乗を9で割ったときの余り

質問

「2の100乗を9で割ったときの余りは？」
の導き方がわかりません。

どうぞよろしくお願いします。

回答No.9

Quattro99 · ベストアンサー

合同式を知らないので、私のやった方法は稚拙ですが。

9で割ると1余る数（「9a+1」と置く）、に9で割るとm余る数（「9b+m」と置く）を掛け合わせると、9a*9b+9a*m+9b+mとなり、これを9で割るとm余ることがわかる。

m=1、つまり、9で割ると1余る数同士を掛け合わせた数を9で割ると1余る。従って、9で割ると1余る数はいくつ掛け合わせても1余る。

2^100を、「9で割ると1余る数」*「9で割るといくつ余るのかわからない数」の積になるように考える。
2^nをn=1から見ていくと、2^6=64が9で割ると1余る数。
100÷6=16余り4なので、2^100=2^(6*16)*2^4である。
2^(6*16)は9で割ると1余る数であり、2^4=16は9で割ると7余る数であるから、2^100を9で割ると7余ることがわかる。

お礼

回答ありがとうございます。
なるほど、とてもわかりやすかったです！

回答No.2

noname#60992

f(n) = 2＾n mod 9
f(n+1) = 2f(n) mod 9

f(0) = 1
f(1) = 2
f(3) = 4
f(4) = 8
f(5) = 16 mod 9 = 7
f(6) = 14 mod 9 = 5
f(7) = 10 mod 9 = 1
ということで、
1→2 →4→8→7→5→1
と循環しています。
ｆ（100）=7
もっと簡単（明快）な方法もあるかも

お礼

回答ありがうございます。
なるほど、なんだかわかってきそうです。
あまりが循環していくというのが理解できました。

回答No.1

info22

2^100=2^(3x33+1)=2*8^33=2*(9-1)^33
二項定理で展開して
=2*(9-1){(9^32)+32(9^31)+(32C2)(9^30)+…+(32C30)(9^2)+32*9+1}
=16*9{(9^31)+32(9^30)+(32C2)(9^29)+…+(32C30)9+32}+16
=16*9{(9^31)+32(9^30)+(32C2)(9^29)+…+(32C30)9+32}+9+7
したがって余りは
7
となります。

お礼

回答ありがとうございます。
数学は高校（あまり記憶にない）以来なので、マゴマゴしていました。
すぐには理解できないのですが、じっくり考えてみます！