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

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

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

No.9 ベストアンサー 回答者： Quattro99 回答日時： 2007/10/02 18:30

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

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余ることがわかる。

この回答へのお礼

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

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

No.13 回答者： snow16 回答日時： 2007/10/14 01:09

いろいろな解き方がありますね。

9=3^2に着目するとこんな解き方もありますよ。
(2^100)mod9
=((3-1)^100)mod9
=(3^100-100*3^99+…+(100*99/2)*3^2-100*3+1)mod9
=7
途中で二項展開を利用し、展開後の最後の2項を除いて9の倍数になっていることを利用しています。

No.12 回答者： ka1234 回答日時： 2007/10/03 21:31

こんにちは。

実際に計算してみました。

　2^100÷9
＝1,267,650,600,228,229,401,496,703,205,376÷9
＝140,850,066,692,025,489,055,189,245,041 余り7

（答え）7

No.11 回答者： stomachman 回答日時： 2007/10/03 01:46

数学としての一般性、汎用性を重んじれば、合同式を使うのが良いと思います。

ですが、2のべき乗の話であるということを活かして、ビジュアルの面白さを楽しむこんな手もあります。

[1] 2^100を２進数で表すと
2^100=[10…0](1の後ろに0が100個並んでいる）
になります。（以下、２進数は[ ]で囲んで表すことにします。）
で、これから1を引き算したものは
2^100-1=[111…1] (1が100個並んでいる）
です。

[2] ところで
2^3-1=7=[111]
2^3+1=9=[1001]
です。両者をかけ算すると、
[111]×[1001]=[111111] (1が6個並んでいる）
になることは一目で分かるでしょう。
（一目じゃ分からない方でも、筆算をやってみたら分かるでしょう。それでも分かんないというのなら、(x-1)(x+1)=(x^2-1)という因数分解の公式を思い出せば、x=2^3のとき、(2^3-1)(2^3+1)=2^6-1=[1000000]-[1] = [111111] と計算できます。）

これにさらに 2^6+1=[1000001]を掛けると
[111111] ×[1000001]=[11…1](1が12個並んでいる） になり、これはもちろん( 2^12-1)です。

さらに 2^12+1=[10…01](0は11個並んでる）を掛けると
[11…1](1が24個並んでる）
となり、これは( 2^24-1)です。

さらに2^24+1=[10…01](0は23個並んでる）を掛ければ
[11…1](1が48個並んでる）
になり、これは( 2^48-1)です。

さらに2^48+1=[10…01](0は47個並んでる）を掛ければ
[11…1](1が96個並んでる）
になり、これは( 2^96-1)です。

[4] さて、これをさらに 2^4=16倍したものは
[11…10000](1が96個並んでる後ろに0が4個ついてる）
です。
ところでこの数は（作り方から明らかなように）9の倍数です。だから、
9X = [11…10000](1が96個並んでる後ろに0が4個ついてる）
と書けます。（実際、X=(2^4)(2^48+1)(2^24+1)(2^12+1)(2^6+1)(2^3-1)ですね。）

[5]9Xに2^4-1=[1111]を足すと、
9X+[1111] = [11…10000]+[1111]=[11…11111]（1が100個並んでる）
になるのも明らかでしょう。
　だから、
(2^100-1)=9X+[1111]
だと分かります。すなわち
(2^100-1)=9X+15
という関係が得られた訳です。左辺の1を移項して整理すると
2^100=9X+15+1 = 9X+16 = 9(X+1)+7
つまり
2^100=9(X+1)+7
です。

[6] ということは
(2^100)÷9=(X+1)余り7
であり、余りは7。また商(X+1)は
(X+1)=(2^4)(2^48+1)(2^24+1)(2^12+1)(2^6+1)(2^3-1)+1
です。

No.10 回答者： zk43 回答日時： 2007/10/02 19:08

ついでにもう一つ

9=2^3+1なので、多項式x^100を多項式x^3+1で割ることを考える。
実際やってみると、
x^100=(x^3+1)(x^97-x^94+x^91-x^88+…+x)-x
となる。
x=2とすれば、
2^100=9(2^97-2^94+2^91-2^88-…+2)-2
=9(2^97-2^94+2^91-2^88-…+2)-9+7
=9{(2^97-2^94+2^91-2^88-…+2)-1}+7
となって余りが7であることが分かる。
カッコの中も等比数列なので、計算できるかも。
最初から等比数列の和の公式を使うことを考えた方が良かったかも
知れません。

この回答へのお礼

回答ありがとうございます。
いろいろと導き方があるのですね！
理解しようとするのが精一杯です。
ありがとうございました。

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

No.8 回答者： zk43 回答日時： 2007/10/02 17:19

典型的なやり方

1,2,3,4,5,6,7,8,9のうち、9と互いに素なものは1,2,4,5,7,8の6個
なので、オイラーの定理より、
2^6≡1（mod 9）
両辺を16乗すると、
2^96≡1（mod 9）
両辺に2^4=16を掛けると、
2^100≡16≡7（mod 9）

この回答へのお礼

回答ありがうございます。
「オイラーの定理」がわかっていませんでした。。
けれど、とてもシンプルに解けるんですね！
ちょっと勉強してみます。

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

No.7 回答者： daikaisan 回答日時： 2007/10/02 16:53

誤操作で、確認画面で直しかけを送ってしまいました。

不細工なことで、すいません。
これからは、別のエディターでキチンと書いてからコピペします。
ドジつづきで、これじゃ似非専門家ですわ。

(９－１)^33＝９^33＋・・・・・・・＋１^33 となって
(９－１)^33＝９×(・・・・・・・)＋１ となって、余り１

更に
２^100＝{９×(・・・・・・・)＋１}×２
２^100＝２×９×(・・・・・・・)＋２
ここでちょいと細工
２^100＝２×９×{(・・・・・・・)＋１－１}＋２
２^100＝２×９×{(・・・・・・・)＋１}－１×９＋２
２^100＝２×９×{(・・・・・・・)＋１}＋７


正しくは、


(９－１)^33＝９^33＋・・・・・・・－１^33 となって
(９－１)^33＝９×(・・・・・・・)－１ となって、余り１

更に
２^100＝{９×(・・・・・・・)－１}×２
２^100＝２×９×(・・・・・・・)－２
ここでちょいと細工
２^100＝２×９×{(・・・・・・・)＋１－１}－２
２^100＝２×９×{(・・・・・・・)－１}＋１×９＋２
２^100＝２×９×{(・・・・・・・)－１}＋７

No.6 回答者： daikaisan 回答日時： 2007/10/02 16:43

補足というか、途中でドジふんでます。

２^100＝２×９×{(・・・・・・・)＋１－１}＋２
２^100＝２×９×{(・・・・・・・)＋１}－１×９＋２
２^100＝２×９×{(・・・・・・・)＋１}＋７

正しくは
２^100＝９×{２×(・・・・・・・)＋１－１}＋２
２^100＝９×{２×{(・・・・・・・)＋１}－１×９＋２
２^100＝２×９×{(・・・・・・・)＋１}＋７

書きくたびれますね、数式はと、言い訳がましいですが・・・。

この回答へのお礼

回答ありがとうございます！
まだ理解はできていないのですが、ゆっくりみていきたいと思います。
いろんな導き方があるんですね！

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

No.5 回答者： daikaisan 回答日時： 2007/10/02 16:35

二項定理やら剰余定理やらと、昔ならったものを

そのままつかって解くのも面白味にかけるので、
中学生に毛の生えた程度でも解ける考えて見ましょう

余りをあらわすには、３２＝９×３＋５　として、５ですね。
これを使いましょ。

次に、
(X+1)^2=X^2+2X+1=X(X+2)+1
(X+1)^3=X^3+3X^2+3X+1=X(X^2+3X+3)+1 で、かっこの中の形が＋１
であれば、(------)が何乗であっても、Xでわったとき、余は１ですね。
２、４、８、１６・・・２の累乗をみてみると、８が利用できそう
８＝９－１だから、さっきの形で余りが、不変の１になるのを使えるね

２^100＝(２^3)^33×２
２^100＝８^33×２
２^100＝(９－１)^33×２

(９－１)^33＝９^33＋・・・・・・・＋１^33 となって
(９－１)^33＝９×(・・・・・・・)＋１ となって、余り１

更に
２^100＝{９×(・・・・・・・)＋１}×２
２^100＝２×９×(・・・・・・・)＋２
ここでちょいと細工
２^100＝２×９×{(・・・・・・・)＋１－１}＋２
２^100＝２×９×{(・・・・・・・)＋１}－１×９＋２
２^100＝２×９×{(・・・・・・・)＋１}＋７

ほい、これでめでたく、余は７となりました。

他にも、解き方はあるけど、書きくたびれたので失礼。

No.4 回答者： joggingman 回答日時： 2007/10/02 15:08

合同式使うと、全部mod9として、

2^100=(2^10)^10=(1024)^10≡7^10≡(-2)^10=1024≡7　(mod9)

この回答へのお礼

回答ありがとうございます。
「合同式」がよくわかっていないのですが、とても簡潔に解けてしますのですね。
勉強してみます！

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