フェルマーの小定理

群の位数

群 $G$ の集合の要素数を、群$G$の位数といって、$|G|$ で表します。

部分群

群$G$の部分集合$H$が群をなしているとき、$H$を$G$の部分群といいます。すなわち、群$G$の部分群$H$は下記の性質を満たします。

1. 任意の $a, b \in H$ に対して, $a \cdot b \in H$
2. $a \in H$ ならば $a^{-1} \in H$

ここで$a^{-1}$は$a$の逆元を表すものとします。

2より$a, a^{-1} \in H$であるから, 1の$b$として$a^{-1}$を選ぶことにより, $a\cdot a^{-1} = e \in H$ (ただし, $e$は $G$の単位元とする) が得られるから, 上の2つの性質は単位元が$H$に存在することを含意する.

また, $G$の演算が結合的なのだから, 当然ながら同じ演算を使う $H$ についても演算は結合的になる.

よって, 1, 2を満たせば, 演算が $H$ に閉じていて, かつ$H$自体が群をなすといえる.

剰余類

群$G$の部分群$H$について, $H = \{e, h_1, h_2, \cdots , h_m \}$ として, $G$の要素$a$に対して積 $aH$ を次のごとく定める:

$$aH = \{ a, a\cdot h_1, a \cdot h_2, \cdots , a\cdot h_m \}$$

この後に証明するように, このように $aH$ を定めるとで部分群 $H$ は群 $G$ の, $aH, bH, cH, \cdots$ というかたちの類別を引き起こす. この同値類を $G$ の $H$ による左剰余類という.

左合同

群$G$の元 $a, b$ に対して, 積 $a^{-1} \cdot b$ が部分群 $H$ に属しているとき, すなわち $a^{-1} \cdot b \in H$のとき, $a$と$b$は$H$を法として左合同であるという.

補題 左合同は同値関係である.

証明 $a$と$b$が$H$を法として左合同であることを$a \sim b$とあらわす.

$H$は部分群であるから, 任意の$aH$に対して逆元$a^{-1} \in H$が存在して, (部分群ゆえに演算が$H$において閉じているから,)

$$a\cdot a^{-1} \in H$$

すなわち,

$$a \sim a$$

である.

$a, b \in G$について, $a^{-1} \cdot b \in H$ であるとき, $H$ は(部分)群なのだからその逆元$(a^{-1} \cdot b)^{-1}=b^{-1} \cdot a$ を含む. すなわち,

$$a^{-1} \cdot b \in H\hspace{10pt}ならば\hspace{10pt}b^{-1} \cdot a \in H$$

よって,

$$a \sim b \hspace{10pt}ならば\hspace{10pt}b \sim a$$

推移律についても,

$a, b, c \in G$について, $a^{-1} \cdot b \in H, b^{-1} \cdot c \in H$ であるならば, $H$は部分群であって乗法が$H$において閉じているのだから,

$$\begin{align} (a^{-1}\cdot b)\cdot (b^{-1} \cdot c) &= a^{-1} \cdot (b \cdot (b^{-1} \cdot c)) \\\ &= a^{-1} \cdot ((b \cdot b^{-1}) \cdot c) \\\ &= a^{-1} \cdot (e \cdot c) \\\ &=a^{-1} \cdot c \in H. \end{align}$$

すなわち,

$$a \sim b\hspace{10pt}かつ\hspace{10pt}b\sim c \hspace{10pt}ならば\hspace{10pt}a\sim c$$

である.

以上より, 左合同は反射律, 対称律, 推移律を満たし, 同値関係である ■

補題 $a$と$b$が$H$を法として左合同であることと, $b \in aH$ は同値である

証明 $a$と$b$が$H$を法として左合同であることを $a\sim b$とあらわす.

$a\sim b$ならば, $a^{-1} \cdot b \in H$ なのだから, ある $h \in H$ が存在して,

$$\begin{align} a^{-1} \cdot b & =h \\\ b &=a\cdot h \in aH \hspace{12pt}(両辺の左からaをかけた) \end{align}$$

逆に, $b \in aH$ ならば, ある $h \in H$ があって,

$$\begin{align} b &= ah \\\ a^{-1} \cdot b &= h \in H \\\ \end{align}$$

すなわち, $a \sim b$.

以上より, $a \sim b$ と $b \in aH$ は同値である ■

上記の補題から, 群$G$は部分群$H$を使って (部分群$H$を法として左合同という関係を使って,) 類別することができて, その同値類は $aH, bH, cH, \cdots$ などと表すことができる.

全単射

群$G$の任意の元$a$は, 部分群$H$を左剰余類$aH$に写す写像 $f_a : H \rightarrow aH$ と見ることができる.

すべての元$h \in H$に対して,

$$f_a (h) = a \cdot h \in aH$$

と定義すると, 明らかに

$$a \cdot h = a \cdot h^\prime \hspace{12pt}ならば\hspace{12pt}h=h^\prime \hspace{10pt}(左からa^{-1}をかけた)$$

なのだから,

$$f_a(h)=f_a(h^\prime ) \hspace{12pt} ならば\hspace{12pt}h=h^\prime$$

であり, 単射である.

また, すべての $a \cdot h \in aH$ について, ある $h^\prime \in H$があって,

$$f_a (h^\prime ) = a \cdot h^\prime = a \cdot h$$

となる ($h^\prime = h$となるように$h^\prime$を取ればいい.)

したがって, $f_a$ は全単射である.

ラグランジュの定理

定理 群$G$の任意の部分群$H$について, $G$を$H$を法として類別した同値類の個数を$[G:H]$として,

$$|G|=[G:H]|H|$$

である.

証明 上の補題から, 部分群$H$を法とする左合同によって群$G$を類別したとき, そのいずれの同値類も (どの$gH (g \in G)$ も, ) $H$ の位数と等しい位数をもつ (元$g$をかけることは全単射$f_g$ を適用することと同一視できるから,)

よって, $G$の位数は$H$の位数と$H$を法とする左合同で類別したときの同値類の個数の積であり,

$$|G|=[G:H]|H|$$

■

このことから, 次のことが系としてしたがう.

系 群$G$の任意の部分群$H$について, $|H| \mid |G|$ ($H$の位数は$G$の位数の約数である.)

巡回群

有限位数の群 (有限群という) $G$の単位元でない元 $g$ について, その冪乗を集めた集合$\{g, g^2, g^3, \cdots \}$は$G$の部分群をなす.

というのも, 群$G$の位数が$|G|$なのだから, このような集合を$|G| + 1$個並べた部分集合

$$\{g, g^2, \cdots , g^{|G|}, g^{|G|+1}\}$$

の中には少なくとも2つ同じ元が含まれる (鳩ノ巣原理.)

それを $g^k, g^l (0 \lt k \lt l \le |G|+1)$ とおくと, 単位元を$e$として,

$$\begin{align} g^k &= g^l \\\ g^{k - l} &= e \hspace{10pt}(0 \lt k - l \le |G|) \end{align}$$

このことから, $\{g, g^2, \cdots , g^{|G|}\}$ には必ず単位元 $e$ が含まれる.

$g^n = e$ とおく. 任意の $0 \le k, l \lt n$ に対して, $m \equiv k+l \pmod{n}$ として, ある$h$があって,

$$g^k \cdot g^l = g^{k+l} = g^{nh + m} = g^{nh}\cdot g^m = g^m$$

であるから, 演算が閉じており, また, 任意の$m$について,

$$g^m \cdot g^{n-m} = g^n = e$$

だから, 逆元が存在する.

明らかに$G$の部分集合であって, 演算が閉じていて逆元が存在するので, $\{g, g^2, \cdots , g^{|G|}\}$ は部分群である. これを$g \in G$によって生成される巡回群といい, $\langle a \rangle$で表す. $g^n = e$ となる$n$が$n \lt |G|$の場合は,

$$\begin{align} &\{g, g^2, \cdots , g^{n-1}, g^n , g^{n+1}, g^{n+2}, \cdots \} \\\ =&\{g, g^2, \cdots , g^{n-1}, e, g, g^2, \cdots \} \\\ =&\{e, g, g^2, \cdots , g^{n-1}\} \end{align}$$

が部分群をなし, このとき, 元$g$ の位数は$n$であるという.

フェルマーの小定理

定理 $p$を素数として, $p$の倍数でない任意の整数$a \in \mathbb{Z}$について,

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

である.

証明 $a=1$のときは, 明らかに $a = 1 \equiv 1 \pmod{p}$ である. 以下, $a \ne 1$ とする.

$\mathbb{Z}/p\mathbb{Z}$は体であるから, $0$ を除いて乗法に関して群をなす. この群を $(\mathbb{Z}/p\mathbb{Z})^{\times}$ とする.

1でない任意の $a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ に対して, 巡回群$\langle a \rangle$は群$(\mathbb{Z}/p\mathbb{Z})^{\times}$の部分群であるから, ラグランジュの定理より, $|\langle a \rangle |$ は $|(\mathbb{Z}/p\mathbb{Z})^{\times}|$ の約数である. すなわち, ある整数 $k$ があって,

$$|(\mathbb{Z}/p\mathbb{Z})^{\times}|=k|\langle a \rangle |$$

よって,

$$a^{|(\mathbb{Z}/p\mathbb{Z})^{\times}|} = a^{k|\langle a \rangle|} = (a^{|\langle a \rangle|})^k = 1^k = 1$$

$(\mathbb{Z}/p\mathbb{Z})^{\times}$ は　$\mathbb{Z}/p\mathbb{Z}$ から $0$ を除いた群であったから,

$$|(\mathbb{Z}/p\mathbb{Z})^{\times}|=p - 1$$

以上より, 群$(\mathbb{Z}/p\mathbb{Z})^{\times}$ においては

$$a^{p-1}=1$$

であり, $a^{p-1} \equiv 1 \pmod{p}$ である ■