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

質問

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

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

回答No.5

WiredLogic

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公式の導出がこんなに大変なものだと知りませんでした。参考書も公式の導出には触れない訳です。

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