数学ゲーム(27) - 非専門的シンギュラリティー研究所

フェルマーの小定理パズル(4)

前回の説明を剰余類の演算を使って書き直します。群論的説明としてはこちらの方が良いのではないかと思います。これも後で検討します。

$\mathbb{Z}$ (整数全体の集合)における $p$ を法とする剰余類を $(p)+n$ とします( $n$ は整数)。剰余類全体 $Z_p = \{ (p)+1,\ (p)+2,\ (p)+3,\ldots ,\ (p)+p-1 \} (= \mathbb{Z}/p\mathbb{Z})$ に加法、減法、乗法を定義することができて、 $Z_p$ は環となります。

フェルマーの小定理

$p$ を素数、 $a$ を $p$ の倍数でない整数( $a$ と $p$ は互いに素)とすると、 $a^{p-1} \equiv 1 \pmod p$

証明(1')

集合 $Z_p = \{(p)+1,\ (p)+2,, \ldots ,\ (p)+p-1 \}$ と写像 $f: Z_p \to Z_p$ 、 $f(k) = (p)+ka$ を考えます。

$f( (p)+i) = f( (p)+j)$ となる $i,\ j \$ ( $0 < i,\ j < p$ ) をとると $(p)+(i-j)a = 0$ となります。 $a$ と $p$ が互いに素なので、 $(p)+i = (p)+j$ となり、 $0 < i,\ j < p$ であることから、 $i=j$ となります。よって写像 $f: Z_p \to Z_p$ は単射となり、 $f$ の像 $f(Z_p)$ の元の個数と $Z_p$ の元の個数は等しくなります。 $f(Z_p) \subseteq Z_p$ で $Z_p$ は有限集合なので $f(Z_p) = Z_p$ となります。

よって写像 $f: Z_p \to Z_p$ は全単射となり、 $(p)+1,\ (p)+2,, \ldots ,\ (p)+p-1$ の順序を入れ替えるだけの写像となるので、すべての $f(i)$ の積 $\displaystyle \prod_{i=1}^{p-1}( (p)+ia)$ は $(p)+1,\ (p)+2, \ldots ,\ (p)+p-1$ の積 $\displaystyle \prod_{i=1}^{p-1}( (p)+i) = (p)+(p-1)!$ と等しくなります。すなわち
$\displaystyle \prod_{i=1}^{p-1}( (p)+ia) = (p)+(p-1)!$
となります。

よって
$\displaystyle (p)+\prod_{i=1}^{p-1} ia = (p)+(p-1)!$
$(p)+(p-1)!\ a^{p-1} = (p)+(p-1)!$
となります。 $p$ が素数であることから、 $p$ と $(p-1)!$ とは互いに素なので、 $(p)+a^{p-1} = (p)+1$ 、よって $a^{p-1} \equiv 1 \pmod p$ が成り立ちます。

証明(2')

「ユークリッドの互除法」によって $f$ が全単射であることを示します。

$a$ と $p$ が互いに素であることからユークリッドの互除法によって $am + pn = 1$ を満たす整数 $m$ と $n$ が存在します。写像 $g: Z_p \to Z_p$ 、 $g( (p)+k) = (p)+km$ を考えます。 $f(g( (p)+k)) = (p)+k$ となるので $f(Z_p) = Z_p$ となります。 $Z_p$ は有限集合なので $f$ は全単射となります。