ちりもつもればミルキーウェイ

好奇心に可処分時間が奪われる

フェルマーの小定理とその証明

数学暗号

はじめに

これは RSA完全理解 Advent Calendar の2日目の記事です(遅刻した)

なんでRSAの話なのにいかにも数学っぽい定理の証明をやるかというと、
RSAの暗号化/復号の操作の証明にはこいつをつかうからです
~~なんならそのうちベズーの等式とかも証明しないといけない~~

それではやっていくぞ

フェルマーの小定理とは

素数 $p$ とその倍数でない正の整数 $a$ について、 $a^{(p-1)}\equiv 1\pmod p$ がなりたつ

という定理です

なぜこいつがわかるとうれしいかについては、次回でRSAの暗号化/復号の操作でこの定理を使って平文に復号できることを証明するので、そこまで楽しみにしておいてください
(ちなみに初等整数論の証明になにかにつけてひょこっと顔出すことも多い印象がある)

ほんまか？

具体例があったほうがイメージしやすいと思うので適当に $a = 5, p = 7$ とかで試してみる

それぞれ条件にあてはめると
$5^{(7-1)}=15625$

剰余をとると
$15625 \bmod 7 = 1$

ほかにもいくつかの例をためすと、条件を満たす $a, p$ をとるとフェルマーの小定理が成り立つことがわかります

証明

方針としては、 $a$ と $p$ が互いに素なとき $a, 2a, 3a, ... (p-1)a$ に対して $p$ で剰余を取るとすべて異なる、という性質を利用します

$a, p$ が互いに素なら $a, 2a, 3a, ... (p-1)a$ を $p$ で剰余を取るとすべて異なる

背理法をつかって証明します
まず $0 \lt j \lt i \lt p$ となる任意の $ia$ と $ja$ をそれぞれの $p$ で割った剰余が同じだと仮定します
そうすると $ia\equiv ja\equiv n\pmod p$ とかけます

$ia, ja$ を $p$ で割った剰余はnですから、 $ia - ja$ をすれば同じ法 $p$ に対して割り切れるはずです( $n - n$ は0なので)

$ia - ja = (i - j)a \equiv 0 \pmod p$

となり $(i-j)a$ が $p$ の倍数となります。
$(i-j)a$ が $p$ の倍数になるためには $a$ が $p$ の倍数である必要があり、これは $a$ と $p$ が互いに素に矛盾します
よって背理法により補題が証明できました

$a$ と $p$ は互いに素なので、補題より $a, 2a, 3a, ... (p-1)a$ の要素を $p$ で剰余をとっていくと $1$ から $p-1$ までの値がすべて1回ずつ登場します。よって

$a\cdot 2a\cdot 3a\cdots (p-1)a \equiv (p-1)! \pmod p$
整理して
$(p-1)!a^{(p-1)} \equiv (p-1)! \pmod p$

条件より法 $p$ は素数なため $(p-1)!$ と互いに素なので両辺を $(p-1)!$ で割ると

$a^{(p-1)} \equiv 1 \pmod p$

これにより題意を示せたので証明終了