15の113乗を7で割った時の余りは

15≡1(mode7)と表せるそうですが、この1はどこから出てきたのでしょうか？

公式からそうなっているということではなくて、根本的なところをを教えて頂きたいです。

No.4 ベストアンサー 回答者： xNekoNyanx 回答日時： 2011/03/05 16:19

No.3の者です。

1を7で割れば「商」は0で、「余り」は1になりませんか？

確かに厳密に突き詰めればこれはちょっとおかしいのですが、なぜ合同式に於いて右辺に最小の数を持ってくるのかと言うと、性質上そのほうが都合が良いからです。

例えば…

※15≡8 (mod 7)

だとして、15のN乗を7で割った余りを求めるのに、8のN乗を考えていたら二度手間ですよね。1なら何乗しても1ですから、可能な限り最小の数値にしておいたほうが問題が少ないわけです。

で、仮に…

※17≡2 (mod 3)

に於いて17の100乗を3で割った余りを求めるとなると、2ですら100乗を計算するのが容易ではないことがわかるでしょう。
この場合は、2の2乗=4がmod 3に於いて1と合同（つまり、4を3で割ったら余りは1）になることを利用して…

※2の2乗≡1 (mod 3)

※2の100乗 = (2の2乗)の50乗

よって

※ (2の2乗)の50乗≡1の50乗 (mod 3)

となり、mod 3に於いてこの「 (2の2乗)の50乗」が「(17の2乗)の50乗（つまり、17の100乗）と合同、すなわち1の50乗と合同となるのです。


簡単に言えば、1のN乗はどこまで行っても1なので、その性質を用いて計算を楽にしてしまおうと言うようなものですかね。

因みに、正しくは…
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
定義：整数aとbを整数mで割ったときの余りが等しいとき，すなわち，a-bがmで割り切れるとき,aとbはmを法として合同であるといい，

a≡b (mod m)

と書く．
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
のようですね。

この回答へのお礼

商0にピンと来ました。1=7×0＋1ということですね。理解できました。

お礼日時：2011/03/05 17:02

No.5 回答者： WiredLogic 回答日時： 2011/03/05 16:53

modeでなく、mod ですよ、というのは、すでに指摘されてますが…

文で書いた問題の、合同式を使わずに説明してみます。
(mCn は、C[m,n]と表すことにします)

15^113 = (2*7+1)^113
= Σ[k=0,113]C[113,k]*(2*7)^(113-k)*1^k
= Σ[k=0,113]C[113,k]*(2*7)^(113-k)

となるのは、大丈夫ですね（２項定理という奴です)

さらに先を計算すると、
15^113 = Σ[k=0,113]C[113,k]*(2*7)^(113-k)
= (2*7)^113 + C[113,1]*(2*7)^112 + C[113,2]*(2*7)^111 + … + C[113,111]*(2*7)^2 + C[113,112]*(2*7) + C[113,113]
になりますが、mCn=C[m,n]は、組み合わせの個数ですから、必ず自然数、
当然、C[113,??]も必ず自然数なので、各項を7で割り切れるかどうかみていくと、
最初の(2*7)^113 から、C[113,112]*(2*7)までは、どれも、*7が入っていて、
それ以外の部分も整数なので、必ず7で割り切れます。
割り切れるかどうかわからないのは、最後のC[113,113]だけですが、この値は１なので、
全体を7で割ると、最後の１の分だけ余る、ということになります。

この２項定理で展開した形から解るように、
自然数a,bがあって、a = b*(整数) + 1 のように表すことができるときは、
aを何乗しても、展開した式の最後の項が1で、途中の式は全部bで割り切れるので、
ｎが0以上の整数なら、必ず、a^n ≡ 1 (mod b) が成り立つことになります。

この回答へのお礼

ありがとうございました。一応理系出身なので内容は、だいたい理解できました。mod公式の導出がこんなに大変なものだと知りませんでした。参考書も公式の導出には触れない訳です。

親切・丁寧な回答に大変感謝致します。

お礼日時：2011/03/05 17:12

No.3 回答者： xNekoNyanx 回答日時： 2011/03/05 11:51

簡単に言えば…

mod A

であれば、Aで割ったときの「余り」が合同であるか、ということです。

この場合は、15を7で割った余りは「1」。同じく1を7で割った余りも「1」なので、「mod 7の時に、15と1は合同」となります。

要するに、そういう定義（決め事）で、なんでそんなことを約束しておかなきゃいけないかというと、タイトルの通り「15の113乗を7で割った時の余り」を求める時などに役に立つ「法則」の土台となるからです。

この回答への補足

ありがとうございます。1を7で割った余りも「1」とありましたが、どう計算をされたか教えて頂けないでしょうか？

15を7で割った余りは「1」は　15＝7×2＋1　となり納得できるのですが・・・

補足日時：2011/03/05 14:54

No.2 回答者： kuriakunn 回答日時： 2011/03/05 11:29

あんまり自信がないのですが説明してみます。

15≡1(mod7)というのは
15を7で割った余りが1ということです。
これはいくらなんでも分かりますよね。

でも、本当に知りたいのは
15^113(mod7)のことですよね。
これ多分15^113≡1(mod7)だと思いますよ。

お望みでないかも知れませんが公式としては
a^n≡b^n（mod k）

証明は「合同式」で検索してみてください。
「根本的なところ」ってのは私には教える実力がありません。

感覚的にはmod7って曜日って感じがしますけどね。

この回答へのお礼

ありがとうございました。

お礼日時：2011/03/05 17:01

No.1 回答者： naniwacchi 回答日時： 2011/03/05 10:26

こんにちわ。

15＝ 14+ 1とでも置き換えてみればよいかと。

この回答へのお礼

ありがとうございます。

お礼日時：2011/03/05 16:57