（3）の解説の意味が分かりません。更にの前までは理解できたのですが、その後が全く分かりません…詳しく

（3）の解説の意味が分かりません。更にの前までは理解できたのですが、その後が全く分かりません…詳しく解説してほしいです。

No.5 回答者： ありものがたり 回答日時： 2020/01/05 20:02

No.1 さんが使っている C の入った記号は、「順列と組み合わせ」の組み合わせです。

nCk で、n 個の異なる物の中から k 個取り出す場合の数を表します。
その nCk が登場するあの公式は、「二項定理」と呼ばれるものです。
重要な定理で、高校生はたいてい知っています。暇なときに調べてみてください。

CHART&SOLUTION に書かれてある
a^n を m で割った余りが (a を m で割った余り)^n を m で割った余りになることは、
二項定理を使わなくても示せます。(使ったほうがスマートですけど)
整数 a,b を m で割ると a = mi + A, b = mj + B, (i,j は整数、A,B は 0,1,2,...,m-1 のどれか)
だとします。すると、ab = (mi + A)(mj + B) = m(mij + Aj + Bi) + AB となります。
mij + Aj + Bi は整数ですから、ab を m で割った余りと AB を m で割ったあまりは一致します。
A,B は a,b を m で割った余りですから、
ab を m で割った余りは (a を m で割った余り)(b を m で割った余り) を m で割った余りです。
これを使って...
(a^0 を m で割った余り) = 1 = (a を m で割った余り)^0 を m で割った余り.
(a^k を m で割った余り) = (a を m で割った余り)^k を m で割った余り　が成り立つとすると、
上記で b = a^n とすることにより
(a^(k+1) を m で割った余り) = (a を m で割った余り)((a を m で割った余り)^k を m で割った余り) を m で割った余り
= (a を m で割った余り)(a を m で割った余り)^k を m で割った余り
= (a を m で割った余り)^(k+1) を m で割った余り　も成り立ちます。
よって、数学的帰納法により、任意の自然数 n について
(a^n を m で割った余り) = (a を m で割った余り)^n を m で割った余り　が成り立ちます。

字数の節約のために、(x を m で割った余り) = (y を m で割った余り) という式を
x ≡ y (mod m) と書きましょうか。
上記の定理は、a ≡ A ならば a^n ≡ A^n (mod m) と書けます。

写真の[3]は、この定理を使って
5^50 = 5^(2・25) = (5^2)^25 = 25^25 ≡ 12^25　(25 ≡ 12 だから)
= 12^(1+2・12) = (12^1)(12^2)^12 = 12・144^12 ≡ 12・1^12　(144 ≡ 1 だから)
= 12　(各 ≡ は mod 13).
と計算しています。

No.1 さんは、
5^50 = 5^(2・25) = (5^2)^25 = 25^25 ≡ (-1)^25　(25 ≡ -1 だから)
= -1 ≡ 12　(各 ≡ は mod 13).
としたほうが良いだろうと言っているわけです。
25 = 13・1 + 12 で余り 12 と見ても
25 = 13・2 - 1 で余り -1 と見ても同じことだ... ということが理解できれば、
こっちのほうが簡明ですね。

No.4 回答者： masterkoto 回答日時： 2020/01/05 17:26

CHART　＆　solution　の内容は

割られる数=商x割る数+あまり　と言う関係（公式）に沿って
a^k=mQ+R…①
R^k=mq+R…②
が成り立つというものです
ただし、Rは割算のあまり、Q、ｑは2つの割り算の商です

（３）について、「更に」以下は
12<13だから（１）のようにはいきません
そこで
12²⁵=12x12²⁴
＝12x(12x12)¹²=12x(12²)¹² ←←←指数法則(12のペア12個は12が全部で24個あることになる）
＝１２ｘ(144)¹²　
として割る数より大きい割られる数144を作っています
①②において
144¹²及び13で割る事が主題となっていますからk=12,m=13として考えるべきだという事はすぐにわかりますよね　
という事でこの時点では
a¹²＝13Q+R…①'
R¹²=13q+R…②'
とできます
Q,qはどうでもいいですがaとRは重要な情報となりますから調べます
144÷13の余り１というのはすぐにわかることなので
割られる数=商x割る数+あまり　の関係にすると
144=１１ｘ13+1です
これをヒントに ②'でR=1としてみますと1¹²=13x0+1です
また①’でa=144としてみると
144¹²=(11x13+1)¹²=(11x13+1)x(11x13+1)x(11x13+1)ｘ・・・(11x13+1)
ここで一度、参考式を考えます
参考：(a+b)(c+d)(e+f)の展開（分配法則)は
a→c→eと掛けて　acdが展開後に現れる項の1つです
a→c→fと掛ければ　acfも展開後に現れる項の1つです
この他にも分配法則で複数の積が現れますが
１つめのカッコから1文字選び、2つ目のカッコからも1文字選び、３つ目のカッコからも1文字選び積にするという作業になりますよね！
このことはカッコの数がさらに増えても同じです
11x13=a,とすれば
(11x13+1)¹²=(a+1)x(a+1)x(a+1)ｘ・・・(a+1)
ですからカッコ3つのときの要領で展開すると
a¹²やa¹¹x1や1¹²などの項が出来ます
aは１３の倍数ですから
aを含む項は13の倍数です
(a+1)x(a+1)x(a+1)ｘ・・・(a+1)の展開でaが付かない項は１¹²だけとなることが分かりますから
144¹²=(aが付く項の和）＋１＝１３の倍数+1です
これを再度：割られる数=商x割る数+あまり　にあてはめてみると
余りは１という事が分かります
つまり、144÷13の余りは１から
144¹²＝13Q+1…①'と
１¹²=13q+１…②'　が導けるのです
要するにここまでで分かることは　144¹²（12²⁴)を13で割る余り１は　
(余り)1¹²を13で割った余り（１）に等しいという事です

次に本来は12x12²⁴の余りを考えるべきだという事に立ち戻ります
144¹²＝13Q+1の両辺を12倍で
12x144¹²＝12x(13Q+1)
⇔12²⁵=13x(12Q)+12…①"
また②'より
１２ｘ１¹²=12(13q+１)=13x(12q)+12…②"
もう1回 割られる数＝商ｘ割る数＋あまり　を思い出して
12²⁵を13で割った余りは12と分かりますが
①',①"と②'②”を用いてsolution流に言えば
12²⁴=144¹²を13で割った余りは１¹²を１３で割った余り１に等しいので
これに12倍して
12²⁵を13で割った余りは（②"を見て）１¹²を１３で割った余り１の12倍になる
と言うのが模範解答の下段が言いたい事なのです


締めに今までの答案を逆順にたどって
１２を１３で割った余り→12²⁵を13で割った余りに等しい→５⁵⁰を13で割った余りに等しい
といえるので、元のあまり（回答終盤で求めたあまり）は12だから逆順にたどり着く答えも12と言う論法です

No.3 回答者： スチールウール 回答日時： 2020/01/05 16:23

25を無理矢理13p+rの形にする

それのべき乗は『二項定理』を使って展開すると、殆どの項（最後のr^n以外）は13を必ず含むので、余りには関係してこない
よって25のべき乗の余りを求められないならr(今回は12)のべき乗の余りを求めても良い

更に12のべき乗の余りを求めるのが厳しいのなら、12=13-1とするか、12^2=13x11+1を利用して同じように+1や-1のべき乗を使って求めれば良い

No.2 回答者： スチールウール 回答日時： 2020/01/05 15:52

>すみません 写真の解説を説明してほしいです

解説していますが？
更に 以降が理解できないと言っているから、25^25(なのか？)の余りは12^25を割った余りで良いことを説明しています
それ理解できたらその次は理解できるはずですし

この回答へのお礼

すみません 式の意味が分からなくて。
なんでCがいきなり出てくるのでしょうか。ほんとにすみません。

お礼日時：2020/01/05 15:54

No.1 回答者： スチールウール 回答日時： 2020/01/05 15:41

25^n=(13+12)^n

=13^n + nC1x13^(n-1)x12 +…+nC1x13x12^(n-1)+12^n
なので、べき乗の数字が見えないですが25^nを13で割った余りは12^nで割った余りに等しい

この問題の場合、そんな解き方するより25 = 26-1として(-1)^nを求めた方が良いとは思うけどね

この回答へのお礼

すみません 写真の解説を説明してほしいです

お礼日時：2020/01/05 15:46