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

今回は有名なフェルマーの小定理を証明していきたいと思います。合同式関連の問題を解く際に結構重宝することが多い印象があるのですが、証明については一回触れて以降あまりやってこなかったので、ここで一度記事にまとめていきたいと思いました。

オイラー関数

フェルマーの小定理を証明するための準備をしていきます。

定義は上のようになるのですが、文字だけだとイメージが湧かないかと思うので、具体例を挙げてみたいと思います。

例1から一般について考えると、法$m$による剰余類$\overline{0},\overline{1},\cdots,\overline{m-1}$の中から代表元を一つずつ取り集めた集合$\{0,1 , \cdots , m-1\}$が完全剰余系になります。(これは$m > 1$な整数であれば、必ず存在します。それについては命題2で証明します)

例2から一般について考えると、法$m$による完全剰余系$\{0,1,\cdots,m-1\}$の中から、$m$と互いに素であるものを集めたものが完全被約剰余系となります。(これは$m > 1$な整数であれば、必ず存在します。これについては命題2で証明します)

オイラー関数はこの完全被約剰余系の個数を表したものです。例2を使って考えると、$\phi(5) = 4$となります。

証明は簡単のため省略します。(いろいろな初等整数論の本でだいたい証明が書かれている気がします)

同様に、下の命題の証明も省略します。これについては、以前投稿した『暗号理論入門(整数3)』という記事で、ユークリッドのアルゴリズムについて扱ったのですが、ここで証明はしていないものの、ユークリッドの互除法がなぜ上手く機能するのかについて説明しています。

記事は下のリンクから
暗号理論入門(整数3)

証明
(1) $S = \{0,1,\cdots,m-1\}$とおく。$n$が整数なら、$n$を$m$で割った余りを$r$とすると、$n \equiv r \mod m$で$r \in S$である。$n$を$m$で割った余りが$r_1 , r_2$の二つが存在したとき、命題1より$r_1 = r_2$である。よって、$S$は完全剰余系である。

($S$は法$m$の剰余類の代表元を集めてできた集合であるので、元の取り方に依らずに代表元と$m$で割った余りと一致する必要がある。well-definedのことです)

$S'$を$S$の元で$m$と互いに素であるもの全体の集合とする。
このとき、$n \in \mathbb{Z} \hspace{1mm},\hspace{1mm}n \equiv r \mod m$なら、定理2より$gcd(n,m) = gcd(r,m)$なので、$n,m$が互いに素であることと、$r,m$が互いに素であることは同値である。よって、$m$と互いに素な$n \in \mathbb{Z}$は$S'$のただ一つの元と$m$を法として合同である。したがって、$S'$は完全被約剰余系である。
(2) $S_1 , S_2$が完全剰余系とする。
$\forall n \in S_1$なら、$S_2$は完全剰余系なので、

$$ n \equiv s \mod m$$

となる$s \in S_2$がただ一つ存在する。ここで、写像$f : S_1 \rightarrow S_2 \hspace{2mm},\hspace{2mm}f(n)=s$と定める。この写像$f$はwell-definedである。
同様に、$S_1$と$S_2$の役割を交換して、写像$g: S_2 \rightarrow S_1 \hspace{2mm},\hspace{2mm}g(s) = n $を定めると、写像$g$もwell-definedである。

$\forall n \in S_1$に対して、$f(n) \equiv n \mod m$であるから、$g(f(n)) = n$となるので、$g \circ f = id_{S_1}$である。同様に、$f \circ g = id_{S_2} $となることが分かる。($id_{S_1},id_{S_2}$は恒等写像を表している)
したがって、$f,g$は逆写像であり、$f$は全単射であるから、$|S_1| = |S_2|$である。

完全被約剰余系についても同様に示すことができる。□

証明
$S = \{x_1,\cdots , x_{\phi(m)}\}$を$1,\cdots,m-1$のなかで$m$と互いに素であるもののすべてとすると、$S$は完全被約剰余系である。

$a,x_i$は$m$と互いに素であるので、その積である$ax_i$も$m$と互いに素である。

よって、

$$ ax_i \equiv x_j \mod m$$

となる$j$がただ一つ存在する。この$x_j$を$f(x_i)$とおく。これによって、写像$f : S \rightarrow S$を定める。

$ax_i \equiv ax_j \mod m$なら、$x_i \equiv x_j \mod m$である。つまり、$x_i = x_j$.よって、写像$f$は単射である。そして、単射であり、$S$は有限集合であるので、$|S| = |f(S)|$である。また、$f(S) \subset S$であるので、$S = f(S)$であることが分かる。(なので、$S\setminus f(S) = \varnothing $)

したがって、写像$f$は全単射である。

$$ a^{\phi(m)}x_1\cdots x_{\phi(m)} \equiv (ax_1)\cdots(ax_{\phi(m)}) \equiv x_1\cdots x_{\phi(m)}$$

となり、$ x_1\cdots x_{\phi(m)}$も$m$と互いに素であることが分かる。したがって、両辺に$x_1\cdots x_{\phi(m)}$の逆元をかけてあげると、結論を得る。□

フェルマーの小定理

ここまでの準備を使って、さくっとフェルマーの小定理を証明したいと思います。

証明
$1,\cdots,p-1$はすべて$p$と互いに素であるので、$\phi(p) = p-1$であることが分かる。

この事実と定理4より、(1)は示せる。

実際、$S = \{1,\cdots,p-1\}$が$p$との互いに素になるもの全体の集合とし、定理4のように写像$f$を定めると、全単射であることが分かり、$x^{p-1}(1\cdots(p-1)) \equiv x(2x)\cdots((p-1)x) \mod p$が成り立つ。両辺$1\cdots p-1$で割ってあげると、$x^{p-1} \equiv 1 \mod p$となる。
(2)$x \not\equiv 0 \mod p$なら、$x^{p-1} \equiv 1 \mod p$が成り立つ。
$x$をもう一度かけると、$x^p \equiv x \mod p$である。
$x \equiv 0 \mod p$なら、$x^p \equiv x \equiv 0 \mod p$.□

今回は以上です。