前へ / 戻る / 次へ

フェルマの小定理

　フェルマ先生は17世紀、フランスの法律家にして数学者です。 その頃は、法律家は論理的に話をしないといけないので数学が必須だったのですね。 パスカル先生やデカルト先生がお友達で、 歴史的難問のフェルマ予想（＝フェルマの大定理）を書き残したことで知られています。
　今から述べるフェルマの小定理は RSA 暗号の動作原理でもあり、 数学全般の基礎となる非常に重要な定理です。

二項係数についての補題

　今日は二項定理を用いた証明を与えましょう。 証明　二項係数は整数であり、分子の素因子 $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,\, 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.9 より $a^p-a = a(a^{p-1}-1)$ は $p$ の倍数であり、$a$ は $p$ と互いに素ですから $a^{p-1}-1$ が $p$ で割り切れます。(証明終) 証明　$a \equiv 0$ ならば $a^e \equiv 0$, $a^f \equiv 0$ ゆえ。そうでなければ、 $e-f = (p-1)\,k\quad$ ( $\exists\, k \in \ZZ$ ) と表せるので Th.12 から $a^e = a^{e-f} \times a^f = \left(a^{p-1}\right)^k \times a^f \equiv 1^k \times a^f \equiv a^f \pmod{p} $ (証明終)

前へ / 戻る / 次へ