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

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

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

No.3 回答者： noname#74443 回答日時： 2007/10/02 15:05

　門外漢ですので、まどろっこしい答え方です。

９で割った余りを考えると
2^1　2
2^2　4
2^3　8
2^4　7
2^5　5
2^6　1
2^7　2
2^8　4
2^9　8
2^10　7

ですから、乗数が６ごとに循環しています。
100(乗)÷6=16…4
　ですから、2^4の余りと同じです。
答えは７

別解
表計算ソフトで9n乗毎の余りをみると
@mod(10^9,9)=8
@mod(10^18,9)=1
@mod(10^27,9)=8
@mod(10^36,9)=1
nが奇数の時の余りは８、従って@mod(2^99,9)=8
従って@mod(2^100,9)は@mod(2^10,9)=7と同じ。
答えは７

この回答へのお礼

回答ありがとうございます。
わかりやすい解説でなるほど！でした。
表計算ソフトでの答えもありがとうございます。

お礼日時：2007/10/02 21:03

No.2 回答者： 16August 回答日時： 2007/10/02 15:04

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
もっと簡単（明快）な方法もあるかも

この回答へのお礼

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

お礼日時：2007/10/02 20:59

No.1 回答者： info22 回答日時： 2007/10/02 15:02

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
となります。

この回答へのお礼

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

お礼日時：2007/10/02 20:54