フェルマーの小定理
$合同式では$ (合同式を参照)$基本性質を利用して\ a^k\ を \ m\ で割った余りを求めました。$
$例えば$
$\qquad 2^{10}\ を \ 7で割った余りは \ \ 7 を法として \quad 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\ が見つかれば計算は非常に簡単になります。$
$例えば \quad 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)$
\begin{eqnarray*} & &n^5-n\\ \\ &=&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 \quad p\ が素数のとき \quad n^p \equiv n \quad (\mod \ \ p)$
$はじめに次の補題を証明します。$
$補題1 \quad _pC_k \ (k=1,2,\cdots,p-1)\ は \ p\ の倍数$
$証明$
$\hspace{2em}p\ は素数だから約数は \ 1\ と \ p\ だけである。$
$\hspace{2em}したがって \ p\ は\ p\ より小さい \ 1,2,\cdots ,p-1\ とは互いに素になるから$
$\hspace{2em}p\ は\ 1 \times 2 \times \cdots \times k=k!\ \ (k=1,\ 2,\ \cdots ,\ p-1)\ と互いに素である。$
$\hspace{2em}また \ \ _pC_k \ \ は整数であるから$
$\hspace{2em} _pC_k=\cfrac{p(p-1)\cdots (p-k+1)}{k!}=p \times \cfrac{(p-1)(p-2)\cdots (p-k+1)}{k!}$
$\hspace{2em}は\ 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}二項定理より$
$\hspace{4em} (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$
$\hspace{2em}補題1より \quad _pC_k\ (k=1,2,\cdots,p-1)\ は \ p\ の倍数だから$
$\hspace{4em} (m+n)^p \equiv m^p+ n^p \quad (mod \ \ p)$
$\hspace{2em}さらに 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*}
$これは数学的帰納法を用いて$
$\hspace{2em} 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)$
$と一般化できます。$
$ここで \quad m_1=m_2=\cdots = m_n=1 \quad とおくと$
$\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)$
$これで定理１が証明されました。$
$これを少し変形すると次の有名な定理が得られます。$
$定理2 フェルマーの小定理$
$\hspace{2em} a\ は整数、p\ は素数で \ \ a,p\ は互いに素のとき$
$\hspace{4em} a^{p-1} \equiv 1 \quad (\mod \ \ p)$
$(注)フェルマーの定理には、大定理(最終定理)と呼ばれている$
$\hspace{4em} n\ が \ 3\ 以上の自然数ならば \quad x^n+y^n=z^n \quad を満たす自然数の解 \ (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$
$\hspace{2em}(1),(2) より \ a\ が整数のとき \quad a^p \equiv a$
$\hspace{2em}よって a^p-a=a(a^{p-1}-1)\ は \ p\ の倍数で、a\ と \ p\ は互いに素だから$
$\hspace{2em}a^{p-1}-1\ は \ p\ の倍数である。$
$\hspace{2em} \therefore a^{p-1} \equiv 1 \quad (mod \ \ p) \hspace{2em}(証明終)$
$\hspace{2em}なお、a^p \equiv a \quad (mod \ \ p)$ で
$\hspace{2em}a\ と \ p\ は互いに素だから、両辺を \ a\ で割って$
$\hspace{2em} 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*} $となって \quad a=1,\ 2,\ \cdots ,\ 6\ で十分であるころがわかります。$
$練習問題を出します。$
$例1 \quad 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 \quad 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 \quad オイラーの定理$
$\hspace{2em} a,\ m\ が互いに素な自然数のとき \qquad a^{\varphi(m)} \equiv 1\ \ (\mod \ \ m)$
$ここに \ \ \varphi(m)\ は \ 1,\ 2,\ \cdots ,\ m\ のうち \ m\ と互いに素な数の個数を表し、オイラー関数と呼ばれています。$
$なお、このオイラー関数とオイラーの定理について$ オイラーの定理(整数論)$を参照してください。$
メインメニュー に戻る