アルゴリズム論特論（塩田）第5回 (4) フェルマの小定理
フェルマの小定理
フェルマ先生は17世紀、フランスの法律家にして数学者です。
その頃は、法律家は論理的に話をしないといけないので数学が必須だったのですね。
パスカル先生やデカルト先生がお友達で、
歴史的難問のフェルマ予想（＝フェルマの大定理）を書き残したことで知られています。
今から述べるフェルマの小定理は RSA 暗号の動作原理でもあり、
数学全般の基礎となる非常に重要な定理です。
Th.9 ( フェルマの小定理 ) $p$ を素数とするとき、$\forall a$ について
$a^p \equiv a \pmod p$
二項係数についての補題
今日は二項定理を用いた証明を与えましょう。
Lemma 10 ( 二項定理 )
$\displaystyle{(x+y)^p = \sum_{k=0}^p \left(\begin{array}{c}p \\ k\end{array}\right) \, x^{p-k}\, y^{k}}$
二項係数 $\displaystyle{\left(\begin{array}{c}p \\ k\end{array}\right)}$ は、
高校では ${}_p C_k$ と書いて、組合せの数と呼んでいたものです。
公式は書けますか？
二項係数 $\displaystyle{\left(\begin{array}{c}p \\ k\end{array}\right)}$ は、
高校では ${}_p C_k$ と書いて、組合せの数と呼んでいたものです。
公式
$\displaystyle{\left(\begin{array}{c}p \\ k\end{array}\right)=\frac{p\,!}{k\,!\,(p-k)\,!}}$
Lemma 11 $p$ を素数、$1 \leqq k \leqq p-1$ とするとき
$\left(\begin{array}{c}p \\ k\end{array}\right) \equiv 0 \pmod p$
証明 二項係数は整数であり、分子の素因子 $p$ は分母には現れないので。(証明終)
フェルマの小定理の証明
Th.9 の証明 $p=2$ のときは $\pmod 2$ で
$a^2 \equiv \left\{
\begin{array}{ll}
0 & \quad \mbox{if }\ \ a \equiv 0 \pmod 2 \\
1 & \quad \mbox{if }\ \ a \equiv 1 \pmod 2 \\
\end{array}
\right.
$
ゆえ。
以下、$p \geqq 3$ とします。$a=0$ のときは
$a^p = 0^p = 0 \equiv a \pmod p$
で成り立ちます。
$a^p \equiv a \pmod p$
を仮定すると、
L'a 10 より
$\displaystyle{(a+1)^p = \sum_{k=0}^p \left(\begin{array}{c}p \\ k\end{array}\right) \, a^{p-k}\, 1^{k}}$
ですが、
L'a 11 より $k=0$, $k=p$ 以外の項は $p$ で割り切れるので
$\displaystyle{(a+1)^p \equiv \left(\begin{array}{c}p \\ 0\end{array}\right) \, a^p + \left(\begin{array}{c}p \\ p\end{array}\right)
\equiv a^p + 1 \equiv a + 1 \pmod p}$
となり、$a+1$ のときも正しくなります。
数学的帰納法により全ての $a \geqq 0$ について正しいことが言えました。
$a \lt 0$ のときは、$-a$ について
$(-a)^p \equiv (-a) \pmod p$
がわかりましたので
$a^p \equiv (-1)^p (-a) = a \pmod p$
(証明終)
Th.12 ( これもフェルマの小定理 ) $p$ が素数で、$a$ が $p$ で割り切れないとき、
$a^{p-1} \equiv 1 \pmod p$
証明 Th.9 より
$a^p-a = a(a^{p-1}-1)$
は $p$ の倍数であり、$a$ は $p$ と互いに素ですから $a^{p-1}-1$ が $p$ で割り切れます。(証明終)