フェルマーの小定理



$合同式では$ (合同式を参照)$基本性質を利用して\ a^kをmで割った余りを求めました。$

$例えば$
$\qquad 2^{10} を 7で割った余りは \ \ 7 を法として \hspace{2em} 2^3=8 \equiv 1\ \ だから$
$\qquad 2^{10}=(2^3)^3 \times 2 \equiv 1^3 \times 2=2$

このような問題では、
$\hspace{2em} a^k \equiv 1 \ \ (mod \ k)$
$となるような kが見つかれば計算は非常に簡単になります。$

例えば $a=3 ,\ m=7 $ では
$\hspace{2em} 3^2 \equiv 2,\ \ 3^3 \equiv 6,\ \ 3^4 \equiv 4,\ \ 3^5 \equiv 5,\ \ 3^6 \equiv 1$
$となって  k=6  です。$

$一般的な、うまい方法があるのでしょうか。$


$はじめに具体的な問題にあたりましょう。$

$nを自然数とします。$
$(1)\quad n^2-n=(n-1)n$
$\hspace{2em} n-1,\ n\ は連続する2数だからどちらか一方は2の倍数$
$\hspace{2em} n^2-n \equiv 0 \quad (mod \ \ 2)$
$\hspace{2em} \therefore n^2 \equiv n \quad (mod \ \ 2)$

$(2)\quad n^3-n=n(n^2-1)=(n-1)n(n+1)$
$\hspace{2em} n-1,\ n,\ n+1 は連続する3数だからどれかは3の倍数$
$\hspace{2em} n^3-n \equiv 0 \quad (mod \ \ 3)$
$\hspace{2em} \therefore n^3 \equiv n \quad (mod \ \ 3)$

$(3)\quad n^5-n$
\begin{eqnarray*} &=&n(n^4-1)\\ &=&n(n^2-1)(n^2+1)\\ &=&(n-1)n(n+1)(n^2-4+5)\\ &=&(n-1)n(n+1)\{(n-2)(n+2)+5\}\\ &=&(n-2)(n-1)n(n+1)(n+2)+5(n-1)n(n+1)\\ \end{eqnarray*} $\hspace{2em} n-2,n-1,n,n+1,n+2  は連続する5数だからどれかは5の倍数$
$\hspace{2em} 5(n-1)n(n+1)  は5の倍数$
 よって
$\hspace{2em} n^5-n \equiv 0 \quad (mod \ \ 5)$
$\hspace{2em} \therefore n^5 \equiv n \quad (mod \ \ 5)$


$一般に次の定理が成りたちます。$


$\qquad 定理1 pが素数のとき n^p \equiv n \quad (mod \ \ p)$


$はじめに次の補題を証明します。$

$補題1 \quad _pC_k \ (k=1,2,\cdots,p-1)\ はpの倍数$

証明
$p\ は素数だから約数は1とpだけである。$
$したがって \ p\ は\ pより小さい \ 1,2,\cdots ,p-1\ とは互いに素になるから$
$p\ は\ 1 \times 2 \times \cdots \times k=k!\ \ (k=1,2,\cdots ,p-1)\ と互いに素である。$

$また \ \ _pC_k は整数であるから$
$\hspace{1em} _pC_k=\cfrac{p(p-1)\cdots (p-k+1)}{k!}=p \times \cfrac{(p-1)(p-2)\cdots (p-k+1)}{k!}$
$は\ p \times (整数)となり\ \ _pC_k\ (k=1,2,\cdots,p-1)\ は\ p\ の倍数となる。$


$補題2 \quad m,n が整数、pが素数のとき、(m+n)^p \equiv m^p+ n^p \quad (mod \ \ p)$

$証明$
$二項定理より$
$\hspace{2em} (m+n)^p=m^p+_pC_1m^{p-1}n +_pC_2m^{p-2}n^2+ \cdots + _pC_{p-1}m\ n^{p-1}+ n^p$

$補題1より \ _pC_k\ (k=1,2,\cdots,p-1)\ はpの倍数だから$

$\hspace{2em} (m+n)^p \equiv m^p+ n^p \quad (mod \ \ p)$


$さらに m_1,\ m_2, \ m_3\ が整数ならば$
\begin{eqnarray*} (m_1+m_2+m_3)^p&=&\{m_1+(m_2+m_3)\}^p\\ & \equiv &m_1^p+(m_2+m_3)^p\\ & \equiv &m_1^p+m_2^p +m_3^p\\ \end{eqnarray*}
$これは数学的帰納法を用いて$

$\quad m_1,m_2,\cdots , m_n が整数、pが素数のとき$

$\hspace{2em} (m_1+m_2+\cdots +m_n)^p \equiv m_1^p+m_2^p+ \cdots + m_n^p \quad (mod \ \ p)$

$と一般化できます。$

$ここで m_1=m_2=\cdots = m_n=1  とおくと$
$\hspace{2em} (1+1+\cdots +1)^p =1^p+1^p+ \cdots +1^p \quad (mod \ \ p)$
$\hspace{2em} \therefore n^p \equiv n \quad (mod \ \ p)$

$これで定理1が証明されました。$


$これを少し変形すると次の有名な定理が得られます。$

$定理2  フェルマーの小定理$
$\hspace{2em} aは整数、pは素数で a,p\ は互いに素のとき$
$\hspace{4em} a^{p-1} \equiv 1 \quad (mod \ \ p)$


$(注)フェルマーの定理には、大定理(最終定理)と呼ばれている$
$\hspace{4em} nが3以上の自然数ならば x^n+y^n=z^n  を満たす自然数の解(x,y,z)は存在しない。$
$\hspace{2em} があり、これと区別するためにこのようによばれています。$

$(証明)$
$(1)\ a>0 のとき$
$\hspace{2em} aは自然数だから定理1でnをaと置き換えて$
$\hspace{2em} a^p \equiv a \quad (mod \ \ p)$

$(2)\ a<0 のとき$
$\hspace{2em} n=-a\ とおくと\ 定理1より$
$\hspace{2em} (-a)^p \equiv -a \quad (mod \ \ p)$
$\hspace{2em} (-1)^p\ a^p \equiv -a$

$\hspace{2em} pは素数だから$
$\quad $(i)$\ \ pが奇素数のとき$
$\hspace{2em} (-1)^p=-1\ より$
$\hspace{2em} -a^p \equiv =-a $
$\hspace{2em} \therefore a^p \equiv a$

$\quad $(ii)$\ p=2\ (2は素数)のとき$
$\hspace{2em}(-1)^2a^2 \equiv -a $
$\hspace{2em} 2a \equiv 0  だから$
$\hspace{2em} a^2 \equiv -a+2a =a$
$\hspace{2em} \therefore a^p \equiv a$

$(1),(2) よりaが整数のとき a^p \equiv a$
$よって a^p-a=a(a^{p-1}-1)\ はpの倍数で、aとpは互いに素だから$
$a^{p-1}-1\ はpの倍数である。$
$\hspace{2em} \therefore a^{p-1} \equiv 1 \quad (mod \ \ p) \hspace{2em}(証明終)$

$なお、a^p \equiv a  \quad (mod \ \ p)$ で
$aとpは互いに素だから、両辺をaで割って$
$\hspace{1em} a^{p-1} \equiv 1 \quad (mod \ \ p)$ としてもよい。


$例えば\ \ p=7\ で確認してみましょう。$
$\hspace{2em} 1^6=1$
$\hspace{2em} 2^6=64 \equiv 1$
$\hspace{2em} 3^6=(3^3)^2=27^2 \equiv (-1)^2=1$
$\hspace{2em} 4^6=(2^2)^6=(2^6)^2 \equiv 1^2=1$
$\hspace{2em} 5^6=(5^3)^2=125^2=(7 \times 18-1)^2 \equiv (-1)^2=1$
$\hspace{2em} 6^6=2^6 \times 3^6 \equiv 1 \times 1 =1$

$となって確かに成りたちます。$

$もちろん\ \ a=7,8,\cdots \ については$
$\hspace{2em} a=b+kp \quad (k は整数、b=0,1,\cdots , p-1)\ とおけるから$
\begin{eqnarray*} a^{p-1}&=&(b+kp)^{p-1}\\ &=&b^{p-1}+_{p-1}C_1b^{p-2}(kp)+ \cdots +_{p-1}C_{p-1}(kp)^{p-1}\\ & \equiv &b^{p-1}\\ \end{eqnarray*} $となって \ a=1,2,\cdots ,6\ で十分であるころがわかりますす。$


$練習問題を出します。$

$例1 10^{20}\ (mod \ \ 17)$

$\hspace{4em} 10^{16} \equiv 1 \ だから$
$\hspace{4em} 10^{20}=10^{16} \times 10^4 \equiv 10^4=17 \times 588+4 \equiv 4$


$例2 10^{20}\ (mod \ \ 13)$

$\hspace{4em} 10^{12} \equiv 1 \ だから$
$\hspace{4em} 10^{20}=10^{12} \times 10^8 \equiv 10^8=(10^2)^4=(13 \times 7+9)^4 \equiv 9^4=81^2=(13 \times 6+3)^2 \equiv 3^2=9$

$となります。$


$ここまでは pが素数であるという条件がついていましが、素数でないとき(合成数といいます)$
$でも成りたつ定理があります。$


$定理3  オイラーの定理$
$\hspace{2em} a,mが互いに素な自然数のとき \qquad a^{\varphi(m)} \equiv 1\ \ (mod \ \ m)$


$ここに \varphi(m)\ は1,2,\cdots ,m\ のうちmと互いに素な数の個数を表し、オイラー関数と呼ばれています。$

$なお、このオイラー関数とオイラーの定理について$ オイラーの定理(整数論)$を参照してください。$




ページの先頭へ↑



メインメニュー に戻る