pCkの素因数とフェルマーの小定理

スポンサーリンク

本項目は発展的内容で、数Ⅱ:式と証明の二項定理や数B:数列の数学的帰納法を学習済みであることを前提としています。

pが素数のとき,{C pk\ (1 k p-1)はpを素因数にもつ.$  $$フェルマーの小定理    ${pが素数のとき,\ {n^p-nはpの倍数である.$    ${pが素数のとき,\ {n^pをpで割るとn余る.$    ${pが素数,\ nとpが互いに素のとき,\ {n^{p-1}をpで割ると1余る.$ { $[l} }\ 2通りの証明方法を下で取り上げた問題でおさえよう. }\ 通常はをフェルマーの小定理というが,\ とを指すこともある. \ この3つを知識として持っておくと,\ 関連問題の見通しがよくなる. \ また,\ これらは合同式で表現すると簡潔である. }\ nを固定してpを変化させた例と,\ pを固定してnを変化させた例を示す. }\ {nは整数,\ pは素数}であることに注意. は2の倍数,\ n³-nは3の倍数,\ n⁵-nは5の倍数,\ ei2^p-2はpの倍数,\ 3^p-3はpの倍数,\ 4^p-4はpの倍数,\ 合同式 n^p≡ n\ od p}  (を移項しただけ) \n²を2で割るとn余る,\ n³を3で割るとn余る,\ n⁵を5で割るとn余る, }\ {合同式 n^{p-1}≡ 1\ od p} の両辺をnで割る.\ n,\ pが互いに素の場合に限り可能) 以下,\ p=7の例のみ示す. なお,\ n,\ pは互いに素なので,\ 7^6や14^6に対しては成り立たない. 「n,\ pが互いに素のとき,\ n^{p-1}-1はpの倍数」}とも考えられる. は7の倍数. フェルマーの小定理の応用例として,\ 7^{102}を11で割ったときの余りを求めてみる. 累乗の余りは循環するわけだが,\ 余り1になる累乗を素早く見つけると楽になる. フェルマーの小定理素数pとk=1,\ 2,\ ,\ p-1に対して,\ C pk\ はpの倍数であること$ $を証明せよ.$ $自然数nについてn^p-nがpの倍数であることを示せ.$ は整数である.$ { }$また,\ 1 k p-1\ より,\ pとk以下の整数は互いに素}である.$ { }$よって,\ 分子のpは,\ 分母のk以下の整数の積に約分されないで残る.$ k^p-kがpの倍数であると仮定する.$ { }{(ii)}\ $また,\ n=k\ のときの仮定より,\ k^p-kはpの倍数}である.$ { }{(ii)}\ $よって,\ n=k+1のときもpの倍数}である.$ $ {全ての自然数nについて,\ n^p-nがpの倍数である.}$ \ 階乗で表された形\ では示せない. \ {連続整数の積の形}にして示すことになる. \ 普段の計算の\ C73={765}{321}\ などを一般化して書いただけである. \ このとき,\ 素数の性質{「素数pは,\ 1,\ 2,\ ,\ p-1と互いに素」}を使う. \ kはp-1以下の整数であるから,\ 素数pは1,\ 2,\ ,\ kと互いに素である. \ 「n⁵-nが5の倍数」は,\ n=5k,\ 5k1,\ 5k2\ として証明した. \ 本問はそれを一般的に示すものであり,\ {数学的帰納法}を用いる. \ n=k+1\ のとき,\ {二項展開}することで,\ {C pk\ と結びつく.} \ 上の解答では,\ C p0=C pp=1,\ 1^n=1\ を適用したものを示した. \ 1が消えるので,\ 残りを\ {C pk をもつものとk^p-kにそれぞれまとめる.} \ と仮定を利用すると,\ いずれの括弧内もpの倍数であることが示される. 素数pと1 k p-1となる整数kについて,\ kC pk=pCp-1}{k-1}を$ $示し,\ C pk はpの倍数であることを証明せよ.$ $素数pに対して,\ 2^pをpで割ったときの余りを求めよ.$ 素数pとkは互いに素 \ 有名な等式の証明で仰々しく見えるが,\ 慣れれば極めて自然な変形である. \ 一般に,\ C pk\ は,\ 階乗を用いて表すことができる. \ 左辺と右辺の階乗の形を考え,\ 一致するように導く. \ ここでは,\ {左辺から右辺を目指して変形}した. \ まず,\ {kとk!\ を約分する}と,\ 分母に(k-1)! ができる.\ 右辺と一致. \ 次に,\ 右辺はpが分離されているから,\ {p! からpを分離する.} \ 後は,\ {p-k=(p-1)-(k-1)}\ と考えると,\ 右辺と完全に一致する. \ 素数の性質{「素数pは,\ 1,\ 2,\ ,\ p-1と互いに素」}を用いる. \ 等式成立時,\ pとkが互いに素ならば,\ C pk がpを素因数にもつはずである. \ C pk\ に結びつけるため,\ 2=1+1と考えて{二項展開}するとし,\ それ以外をまとめる. \ より,\ 括弧内はpの倍数となるから,\ 残りが余りである. \ 答えるとき,\ {場合分けを要する}ことに注意する. \ 2で割ったときの余りだけは,\ 0か1で答えなければならないのである. \ 一般に,\ 「n^pをpで割るとn余る」は,\ {n=pのときだけは余り0}である.
タイトルとURLをコピーしました