本項の内容は、数Ⅱ：式と証明の二項定理や数B：数列の数学的帰納法を学習済みであることを前提としています。
pが素数のとき,\ \ C pk\ (1≦ k≦ p-1)はpを素因数にもつ.$
$[2]$\ \ フェルマーの小定理（\,$n：整数$\,）
①\ \ $pが素数のとき n^p-n ≡ 0\ ±od p$
②\ \ $pが素数のとき n^p≡ n\ ±od p$ (\,$n$を移項した\,)
③\ \ $pが素数,\ nとpが互いに素のとき n^{p-1}≡ 1\ ±od p}
[1]}\ \ フェルマーの小定理の証明にこの定理を利用する.
\ \ 2通りの証明方法があるので,\ 後に示す問題で確認してほしい.
[2]}\ \ 通常,\ フェルマーの小定理といえば,\ ③のことを指す.
\ \ 高校数学では,\ 同値な①,\ ②の表現で登場することが多い.
[2]}\ \ ①\ \ n^p-nはpの倍数}である.
[2]}\ \ ①}\ \ \rei\ \ n^2-nは2の倍数,\ n^3-nは3の倍数,\ n^5-nは5の倍数,\ ･･････ (超頻出)
[2]}\ \ ①}\ \ \rei\ \ 2^p-2はpの倍数,\,\ 3^p-3はpの倍数,\,\ 4^p-4はpの倍数,\ ･･････
[2]}\ \ ②\ \ n^p\,をpで割った余りとnをpで割った余りは等しい.}
[2]}\ \ ①}\ \ \rei\ \ n^5\,を5で割った余りとnを5で割った余りは等しい.
[2]}\ \ ①}\ \ \rei\ \ 3^p\,をpで割った余りと3をpで割った余りは等しい.
[2]}\ \ ③\ \ n^{p-1}\,をpで割ると1余る.}\ \ 合同式は,\ ②のn^p≡ nの両辺をnで割って得られる.
[2]}\ \ ①}\ \ nとpが互いに素のとき,\ nx≡ ny\ ⇔\ x≡ y±od p}\ が成り立つのであった.
[2]}\ \ ①}\ \ \rei\ \ 2^6\,を7で割ると1余る,\ 3^6\,を7で割ると1余る,\ 4^6\,を7で割ると1余る,\ ･･････
[2]}\ \ ①}\ \ n^{p-1}-1≡0±od p}\ ととらえることもできる.
[2]}\ \ ①}\ \ \rei\ \ 2^{6}-1は7の倍数,\ 3^{6}-1は7の倍数,\ 4^{6}-1は7の倍数,\ ･･････
フェルマーの小定理の最も代表的な応用例として,\ 累乗数の余りを求める}ことがある.
例として,\ 7^{102}\,を11で割ったときの余りを求めてみよう.
このとき,\ 11で割ったときの余りが1になるような7の累乗数が見つかれば簡潔に済むのであった.
フェルマーの小定理を利用することで,\ 実際に計算することなく見つけ出すことができる.
フェルマーの小定理③より 7^{10}≡1±od{11}
よって 7^{102}=(7^{10})^{10}･7^2≡1^{10}･49≡5\ ±od{11
$n$が3以上の整数のとき,\ $C n3$が$3$の倍数となるための必要十分条件を求めよ.
(2)\ \ $n$が3以上の整数のとき,\ $C n3$が$n$の倍数となるための必要十分条件を求めよ.
(3)\ \ $C{100}{50}$がもつ素因数3の個数を求めよ. \\
3数$n,\ n-1,\ n-2$は連続する3整数}である.
よって,\ 3数のうち少なくとも1つは偶数,\ いずれか1つが3の倍数である.
ゆえに,\ 3数のうちいずれか1つが$3^2=9$の倍数となる}ことが条件である.
∴$ 3以上の整数$n$に対して$n≡0,\ 1,\ 2±od9}$\ が求める条件である.} 2数$n-1,\ n-2$は連続する2整数}である.
よって,\ 2数のうち少なくとも1つは偶数である.
ゆえに,\ 2数のうちいずれか1つが$3$の倍数となる}ことが条件である.
∴$ 3以上の整数$n$に対して$n≡1,\ 2±od3}$\ が求める条件である.} \\
(3)\ \ $C{100}{50}=100!}{50!･50!$ $xを超えない最大の整数を\gauss xで表す 100C50 がもつ素因数3の個数は
二項係数\,C pk\,は,\ 連続整数の積または階乗を用いて表現できる.}
C pk\,の倍数性や素因数の個数について考察するとき,\ どちらの表現を利用するかの選択に迫られる.
(1)\ \ 連続整数の積による表現で考えると,\ n(n-1)(n-2)が18の倍数であることが条件とわかる.
\ \ 2と9は互いに素なので,\ 2の倍数かつ9の倍数となる条件を考える.
\ \ 2の倍数であることは明らかなので,\ 後は9の倍数条件である.
\ \ 3数のうち3の倍数はいずれか1つのみなので,\ これが9の倍数であることが条件}である.
\ \ つまり,\ n=9m\ または\ n-1=9m\ または\ n-2=9m}\ が条件である.
\ \ n=9m,\ 9m+1,\ 9m+2\ (m:整数)となるが,\ 合同式で表すと簡潔になる.
(2)\ \ (1)と同様に考えると,\ n-1=3m\ または\ n-2=3m}\ が条件となる.
\ \ n≡1,\ 2±od3は,\ nが3の倍数でない}と言い換えることができる.
(3)\ \ 階乗による表現で考えると,\ 階乗の素因数の個数の問題}に帰着する.
\ \ 階乗の素因数の個数の求め方は当カテゴリの序盤で解説済みなので,\ ここでは解説しない.
\ \ 分子には3が48個,\ 分母には3が44個あるから,\ 44個が約分されて分子に4個だけが残る.
$素数pとk=1,\ 2,\ ･･･,\ p-1に対して,\ C pk\ はpの倍数であることを証明せよ.$
(2)\ \ $整数nと素数pに対して,\ n^p-nはpの倍数であることを示せ.$
(3)\ \ $整数n$と素数$p$が互いに素であるとき,\ $n^{p-1}-1$が$p$の倍数であることを示せ.
$ここで,\ 1≦ k≦ p-1\ より,\ pとk以下のすべての整数は互いに素}である.$
$よって,\ 分子のpは,\ 分母のk以下のすべての整数の積に約分されないで残る.$
$一方,\ C pk\,は異なるp個のものからk個を選ぶ場合の数であるから整数}である.
連続整数の積による表現}で考えるとわかりやすい.
分子にpが残ることと\,C pk\,が整数であることを示す}と題意が示される.
素数の性質「素数pは,\ 1,\ 2,\ ･･･,\ p-1のすべてと互いに素」}を利用することになる.
C pk\,が整数であることの証明は,\ 場合の数の観点から簡潔に述べておく方法が有名である.
C 42=6≠(4の倍数)のように,\ pが素数でない場合には成り立たない.
n=1}のとき n^p-n=1^p-1=0はpの倍数}である.${n=k}\,のとき k^p-kがpの倍数}であると仮定する. n=k\ のときの仮定より,\ k^p-kはpの倍数}である.$
(ii)}\ \ $よって,\ (k+1)^p-(k+1)はpの倍数}である.すべての自然数$n$に対して,\ $n^p-n$は$p$の倍数である.
[2]\ \ $n=0}$のとき $0^p-0=0はpの倍数}である.$ $n$が負の整数}のときp=2}$のとき $n^2-n=n(n-1)$は連続2整数の積なので2の倍数}である.
(ii)\ \ $pが3以上の奇素数}$のとき
$m^p-m$は$p$の倍数}であるから,\ $n^p-nもpの倍数}である.すべての整数nに対して,\ n^p-nはpの倍数である.}$}
フェルマーの小定理の別表現\ n^p-n≡0±od p\ の証明であり,\ 数学的帰納法}を利用する.
nを自然数とする設定が多いが,\ 本問は整数nについての証明}であることに注意する.
整数問題では,\ 先に自然数の場合を示し,\ それを元に整数の場合にまで拡張する}手法が有効である.
n=k+1\ のとき,\ (k+1)^p\,を二項展開}することにより,\ C pk\,のpの倍数性と結びつく.}
整理して(1)と仮定を考慮すると各項がpの倍数となるから,\ 全体もpの倍数である.
nが負の整数のとき,\ n=-\,mと置換することで自然数mについての式に書き換えられる.}
ここで,\ pが偶数のとき(-\,m)^p=m^p,\ \ pが奇数のとき(-\,m)^p=-\,m^p\,である.
よって,\ 場合分けする必要が生じる.\ ただし,\ pは素数なので,\ 偶数は2のみである.
問われることは稀だが,\ 以下のような別解も知られている.(a+b)^p≡ a^p+b^p±od p ･･････\,( B)
( B)においてbをb+cに置き換えると \{a+(b+c)\}^p≡ a^p+(b+c)^p
( B)より(b+c)^p≡ b^p+c^p±od pも成り立つから (a+b+c)^p≡ a^p+b^p+c^p±od p
これを繰り返すことにより (a_1+a_2+･･･+a_n)^p≡ {a_1}^p+{a_2}^p+･･･+{a_n}^p±od p
a_1=a_2=･･･=a_n=1とすると (1+1+･･･+1)^p≡ 1^p+1^p+･･･+1^p±od p
よって n^p≡ n±od p
(3)\ \ (2)より,\ $n(n^{p-1}-1)$は$p$の倍数である.
$n$と$p$は互いに素}なので,\ $n^{p-1}-1はpの倍数}$である.
$kn,\ ln$を$p$で割ったときの余りが等しいと仮定}する.
このとき,\ $ln-kn=n(l-k)$が$p$で割り切れるはずである.
ところが,\ $nとpは互いに素}$であり,=””=”” \=”” \=”” よって,\=”” $n(l-k)$が$p$で割り切れることはない.\=”” これは矛盾}である.=”” ゆえに,n,\=”” 2n,\=”” 3n\=”” ･･･,\=”” (p-1)n$を$p$で割ったときの余りはすべて異なる}($p≧2$).=””=”” ここで,\=”” $p-1$個の整数$n,\=”” 3n,\=”” (p-1)n$は$p$の倍数ではない.=”” $p$で割った余りには,\=”” $1,\=”” p-1のp-1$種類の余りが1回ずつ現れる.}$(p-1)!$と$p$は互いに素}なので$(p-1)!$で割ると $n^{p-1}≡1±od=”” p}$}=”” フェルマーの小定理n^{p-1}≡1±od=”” pの証明であり,\=”” (2)から直ちに示される.=”” 試験では(1),\=”” (2)を利用して示すが,\=”” 本来は完全剰余系の基本定理}を利用して証明する.=””=”” pとnが互いに素であるとき,\=”” n,\=”” pnをpで割ったときの余りはすべて異なる.=”” ax+by=”1の整数解の存在証明の際に詳しく解説したので,\” ここでは簡単な解説に留める.=”” 本問の場合は,\=”” (p-1)nまでのp-1個の整数をpで割ったときの余りがすべて異なることを示す.=”” 「\,pで割ったときの余りが等しい\=” 差がpの倍数」を利用し,\=”” 背理法}で示す.=”” の両辺を足すと矛盾を示すにはp≧3で考える必要があるが,\=”” p=”2のときにも成り立つことは明らかである.” nとpは互いに素なので,\=”” (p-1)nをpで割ったときの余りが0になることはない.=”” また,\=”” 余りはすべて異なるから,\=”” p-1個の整数とp-1種類の余りが1対1で対応する}とわかる.=”” p-1個の整数n,\=”” (p-1)nをすべて掛け合わせる.}=”” どの整数と余りが対応しているかは不明だが,\=”” それらの余りは1からp-1までの整数の積}となる.=”” 素数pは1,\=”” 2,\=”” p-1のすべてと互いに素なので,\=”” その積(p-1)!\,とも互いに素である.=”” 素数pと1≦=”” k≦=”” p-1となる整数kについて,\,はpの倍数であることを証明せよ.$=”” (2)\=”” $素数pに対して,\=”” 2^p\,をpで割ったときの余りを求めよ.$=”” (3)\=”” 3^p\,をpで割ったときの余りを求めよ.{素数pと整数kは互いに素}である.$=”” \$3^p$を$p$で割ったときの余りは$2^p+1$を$p$で割ったときの余りと一致}する.=”p=”2のとき\”” 余り1,\=”” 余り0,\=”” p≧5のとき\=”” 余り3}$}=”” (1)\=”” 左辺と右辺の二項係数をそれぞれ階乗で表して一致することを示せばよい.=”” \=”” pC{p-1}{k-1}\,がpの倍数よりkC=”” pk\,もpの倍数だが,\=”” p,\=”” kは互いに素なので\,C=”” pk\,がpの倍数である.=”” (2)\=”” フェルマーの小定理の別表現n^p≡=”” n±od=”” pの特別な場合である.=”” 2=”1+1}と考えて二項展開}すると,\” C=”” pk\,の倍数性と結びつく.=”” 2^p≡=”” 2±od=”” pが導かれるが,\=”” 安易に余りを2と答えてはならない.=”” pで割ったときの余りはp-1以下の自然数}である.=”” pが3以上の素数の場合は余り2だが,\=”” (3)\=”” 3=”2+1}と考えて二項展開}すると,\” (2)に帰着する.=”” pで割ったときの余りはp-1以下の自然数であることに注意して答える
