検索用コード
pが素数}}のとき,\ \ \bm{\textcolor{red}{\kumiawase pk\ (1\leqq k\leqq p-1)はpを素因数にもつ.}}$ \\\\  $[2]$\ \ \textbf{\textcolor{blue}{フェルマーの小定理}} \\[.5zh]    \maru1\ \ $\bm{\textcolor{cyan}{pが素数}}のとき,\ \bm{\textcolor{red}{n^p-nはpの倍数}}である.$ \\[.5zh]    \maru2\ \ $\bm{\textcolor{cyan}{pが素数}}のとき,\ \bm{\textcolor{red}{n^pをpで割るとn余る.}}$ \\[.5zh]    \maru3\ \ $\bm{\textcolor{cyan}{pが素数,\ nとpが互いに素}}のとき,\ \bm{\textcolor{red}{n^{p-1}をpで割ると1余る.}}$ \\\\[1zh] \centerline{{\normalsize $\left[\textcolor{brown}{\begin{array}{l} \text{[1]}\ 2通りの証明方法を下で取り上げた問題でおさえよう. \\[1zh] \text{[2]}\ 通常は\maru3をフェルマーの小定理というが,\ \maru1と\maru2を指すこともある. \\ \phantom{[1]}\ この3つを知識として持っておくと,\ 関連問題の見通しがよくなる. \\ \phantom{[1]}\ また,\ これらは合同式で表現すると簡潔である. \\ \phantom{\text{[2]}}\ nを固定してpを変化させた例と,\ pを固定してnを変化させた例を示す. \\ \phantom{\text{[2]}}\ \bm{nは整数,\ pは素数}であることに注意. は2の倍数,\ n^3-nは3の倍数,\ n^5-nは5の倍数,\ \cdots\cdots \\ ei\ \ 2^p-2はpの倍数,\ 3^p-3はpの倍数,\ 4^p-4はpの倍数,\ \cdots\cdots \\[1zh] 合同式 n^p\equiv n\ \pmod p}  (\maru1を移項しただけ) \\ \ n^2を2で割るとn余る,\ n^3を3で割るとn余る,\ n^5を5で割るとn余る, \text{[2]}\ \maru3\ \ \bm{合同式 n^{p-1}\equiv 1\ \pmod p} \\ の両辺をnで割る.\ n,\ pが互いに素の場合に限り可能) \\ 以下,\ p=7の例のみ示す. なお,\ n,\ pは互いに素なので,\ 7^6や14^6に対しては成り立たない. \\ 「n,\ pが互いに素のとき,\ n^{p-1}-1はpの倍数」}とも考えられる. \\ は7の倍数. \\[1zh] フェルマーの小定理の応用例として,\ 7^{102}を11で割ったときの余りを求めてみる. \\ 累乗の余りは循環するわけだが,\ 余り1になる累乗を素早く見つけると楽になる. \\ フェルマーの小定理素数pとk=1,\ 2,\ \cdots,\ p-1に対して,\ \kumiawase pk\ はpの倍数であること$ \\[.2zh] \hspace{.5zw}\phantom{(1)}\ \ $を証明せよ.$ \\[1zh] \hspace{.5zw}(2)\ \ $自然数nについてn^p-nがpの倍数であることを示せ.$ \\ は整数である.$ \\[.5zh] \phantom{ (1)}\ \ $また,\ 1\leqq k\leqq p-1\ より,\ \textcolor{cyan}{pとk以下の整数は互いに素}である.$ \\[.2zh] \phantom{ (1)}\ \ $よって,\ 分子のpは,\ 分母のk以下の整数の積に約分されないで残る.$ \\[1zh] k^p-kがpの倍数であると仮定する.$ \\[1zh] \phantom{ (1)}\ \ \phantom{(ii)}\ $また,\ n=k\ のときの仮定より,\ \textcolor{magenta}{k^p-kはpの倍数}である.$ \\[.2zh] \phantom{ (1)}\ \ \phantom{(ii)}\ $よって,\ n=k+1のときも\textcolor{red}{pの倍数}である.$ \\[1.5zh] \centerline{$\therefore \bm{全ての自然数nについて,\ n^p-nがpの倍数である.}$ (1)\ 階乗で表された形\ では示せない. \\ \phantom{(1)}\ \bm{連続整数の積の形}にして示すことになる. \\ \phantom{(1)}\ 普段の計算の\ \kumiawase73=\bunsuu{7\cdot6\cdot5}{3\cdot2\cdot1}\ などを一般化して書いただけである. \\ \phantom{(1)}\ このとき,\ 素数の性質\bm{「素数pは,\ 1,\ 2,\ \cdots,\ p-1と互いに素」}を使う. \\ \phantom{(1)}\ kはp-1以下の整数であるから,\ 素数pは1,\ 2,\ \cdots,\ kと互いに素である. \\[1zh] (2)\ 「n^5-nが5の倍数」は,\ n=5k,\ 5k\pm1,\ 5k\pm2\ として証明した. \\ \phantom{(1)}\ 本問はそれを一般的に示すものであり,\ \bm{数学的帰納法}を用いる. \\ \phantom{(1)}\ n=k+1\ のとき,\ \bm{二項展開}することで,\ \bm{\kumiawase pk\ と結びつく.} \phantom{(1)}\ 上の解答では,\ \kumiawase p0=\kumiawase pp=1,\ 1^n=1\ を適用したものを示した. \\ \phantom{(1)}\ 1が消えるので,\ 残りを\ \bm{\kumiawase pk をもつものとk^p-kにそれぞれまとめる.} \\ \phantom{(1)}\ (1)と仮定を利用すると,\ いずれの括弧内もpの倍数であることが示される. 素数pと1\leqq k\leqq p-1となる整数kについて,\ k\kumiawase pk=p\kumiawase{p-1}{k-1}を$ \\[.2zh] \hspace{.5zw}\phantom{(1)}\ \ $示し,\ \kumiawase pk はpの倍数であることを証明せよ.$ \\[1zh] \hspace{.5zw}(2)\ \ $素数pに対して,\ 2^pをpで割ったときの余りを求めよ.$ \\ 素数pとkは互いに素 (1)\ 有名な等式の証明で仰々しく見えるが,\ 慣れれば極めて自然な変形である. \\ \phantom{(1)}\ 一般に,\ \kumiawase pk\ は,\ 階乗を用いて表すことができる. \phantom{(1)}\ 左辺と右辺の階乗の形を考え,\ 一致するように導く. \\ \phantom{(1)}\ ここでは,\ \bm{左辺から右辺を目指して変形}した. \\ \phantom{(1)}\ まず,\ \bm{kとk\kaizyou\ を約分する}と,\ 分母に(k-1)\kaizyou ができる.\ 右辺と一致. \\ \phantom{(1)}\ 次に,\ 右辺はpが分離されているから,\ \bm{p\kaizyou からpを分離する.} \\ \phantom{(1)}\ 後は,\ \bm{p-k=(p-1)-(k-1)}\ と考えると,\ 右辺と完全に一致する. \\[1zh] \phantom{(1)}\ 素数の性質\bm{「素数pは,\ 1,\ 2,\ \cdots,\ p-1と互いに素」}を用いる. \\ \phantom{(1)}\ 等式成立時,\ pとkが互いに素ならば,\ \kumiawase pk がpを素因数にもつはずである. \\[1zh] (2)\ \kumiawase pk\ に結びつけるため,\ 2=1+1と考えて\bm{二項展開}するとし,\ それ以外をまとめる. \\ \phantom{(1)}\ (1)より,\ 括弧内はpの倍数となるから,\ 残りが余りである. \\ \phantom{(1)}\ 答えるとき,\ \bm{場合分けを要する}ことに注意する. \\ \phantom{(1)}\ 2で割ったときの余りだけは,\ 0か1で答えなければならないのである. \\ \phantom{(1)}\ 一般に,\ 「n^pをpで割るとn余る」は,\ \bm{n=pのときだけは余り0}である.