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

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

前回の議論で

$\mathbb{Z}$ における $p$ を法とする剰余類全体 $\mathbb{Z}/p\mathbb{Z}$ が体であること、
$\mathbb{Z}/p\mathbb{Z}$ から $0$ を除いた $(\mathbb{Z}/p\mathbb{Z})^\times$ が乗法に関して群であること

がわかりました。

有限群 $G$ の元の個数を $|G|$ と表します。

ラグランジュの定理

有限群 $G$ とその部分群 $H$ に対して
$|G| = |G:H| \cdot |H|$
が成り立ちます。

$|G:H|$ は $H$ に関する左剰余類または右剰余類の個数を表します。これは証明の中で説明します。

証明

$|H| = n$ 、 $H = \{h_1, h_2, \cdots, h_n\}$ とします。

$f: G \to \mathfrak{P}(G)$ ( $\mathfrak{P}(G)$ は $G$ のべき集合)を $x \mapsto xH$ という写像とします。 $f$ の像 $f(G)$ の元の個数を $m$ 、 $f(G) = \{C_1, C_2, \cdots, C_m\}$ とします( $G$ の部分集合として $f^{-1}(C_j) = C_j$ で、 $G$ はこれらの共通部分のない集合に分割されます)。各 $C_j$ から1個ずつ元 $c_j$ をとります。

$x \in G$ に対して $xH = C_j$ となる $C_j$ が存在し、 $x \in C_j = c_jH$ より $x = c_j h_i$ となる $h_i$ が存在します。

$c_j h_i = c_{j'} h_{i'}$ とすると、
$C_j = c_j H = c_j h_i H = c_{j'} h_{i'} H = c_{j'} H = C_{j'}$
$c_j = c_{j'}$
$h_i = c_j^{-1} c_j h_i = c_j^{-1} c_{j} h_{i'} = h_{i'}$
となります。

よって

$G = \{c_j h_i \mid i = 1, 2, \cdots, n; \ j = 1, 2, \cdots, m\}$
$c_j h_i = c_{j'} h_{i'}$ ならば $i = i'$ かつ $j = j'$

となり $G$ の元の個数は $mn$ となります。

次に $g: G \to \mathfrak{P}(G)$ を $x \mapsto Hx$ という写像とします。 $g$ の像 $g(G)$ の元の個数を $m'$ 、 $g(G) = \{D_1, D_2, \cdots, D_{m'}\}$ とします( $G$ の部分集合として $g^{-1}(D_j) = D_j$ で、 $G$ はこれらの共通部分のない集合に分割されます)。各 $D_j$ から1個ずつ元 $d_j$ をとります。

$x \in G$ に対して $Hx = D_j$ となる $D_j$ が存在し、 $x \in D_j = Hd_j$ より $x = h_i d_j$ となる $h_i$ が存在します。

$h_i d_j = h_{i'} d_{j'}$ とすると、
$D_j = H d_j = H h_i d_j = H h_{i'} d_{j'} = H d_{j'} = D_{j'}$
$d_j = d_{j'}$
$h_i = h_i d_j d_j^{-1} = h_{i'} d_j d_j^{-1} = h_{i'}$
となります。

よって

$G = \{h_i d_j \mid i = 1, 2, \cdots, n; \ j = 1, 2, \cdots, m'\}$
$h_i d_j = h_{i'} d_{j'}$ ならば $i = i'$ かつ $j = j'$

となり $G$ の元の個数は $m'n$ となります。

よって $m = m'$ となります。

$|H:G| = m = m'$ と定義します。

系1

有限群 $G$ とその部分群 $H$ に対して $|H|$ は $|G|$ の約数となります。

系2

有限群 $G$ の元 $x$ に対して $x^{|G|} = e$

系2の証明

$x \in G$ とすると
$x, x^2, x^3, \cdots$
の中に $x^i = x^j$ となる $x^i$ 、 $x^j$ が存在します。 $x^{i-j} = e$ となります。

$x^{n} = e$ を満たす最小の正の自然数を $n$ とします。 $\{e, x, x^2, x^3, \cdots, x^{n-1}\}$ は元の個数が $n$ の $G$ の部分群となります。系1より $n$ は $|G|$ の約数となり $|G| = nm$ となる $m$ が存在します。よって
$x^{|G|} = x^{nm} = (x^{n})^m = e^m = e$
となります。

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

$p$ を素数、 $a$ を $p$ の倍数でない整数( $a$ と $p$ は互いに素)とします。系2を $(\mathbb{Z}/p\mathbb{Z})^\times$ に適用すると
$( (p)+a)^{p-1} = (p)+1$
$(p)+a^{p-1} = (p)+1$
よって
$a^{p-1} \equiv 1 \pmod p$
が成り立ちます。