オイラーの φ-関数とF_pの乗法群の生成元の割合について

ここではオイラーの $\varphi$ 関数と $\mathbb{F}_p$ の乗法群の生成元の割合について簡単にまとめたいと思います.

オイラーの $\varphi$ 関数は素朴な定義なのに整数論では頻繁に出てくる大事な関数だと思います.

ではまずは定義からです.

定義 1. $\mathbb{N} \ni n \geq 2$ に対して, $1, \cdots, n$ のなかで $n$ と互いに素なものの個数を $\varphi(n)$ とかく. この $\varphi(n)$ をオイラーの $\varphi$ 関数という.

例 $\varphi(2)=1, \varphi(3)=2, \varphi(4)=2, \varphi(5)=4, \varphi(6)=2, \varphi(7)=6, \varphi(8)=4, \varphi(9)=3, \varphi(10)=4, \cdots$

この値の観察として, $n=p^k$ という素数のベキのときは, $1 \leq i \leq p^k$ が $p^k$ と互いに素ということは $p$ と互いに素ということと同値なので $\varphi(p^k)=p^k- \dfrac{p^k}{p}=p^{k} \left( 1- \dfrac{1}{p} \right)$ となります.

命題 2. $p$ を素数, $k \in \mathbb{N}$ とする. このとき

$\varphi(p^k) = p^{k} \left( 1-\dfrac{1}{p} \right)$

実際上の例でみても $\varphi(4)=\varphi(2^2)=4 \cdot \left( 1- \dfrac{1}{2} \right) = 2, \varphi(9)=\varphi(3^2)=9 \cdot \left( 1- \dfrac{1}{3} \right) =3$ となっています.

また次の事実をふまえるといろんなことがわかります.

命題 3. $m, n \in \mathbb{N}$ とする. 次が成り立つ.

$(1)$ $m, n$ が互いに素 $\Longleftrightarrow$ $am+ bn=1$ となる整数 $a, b$ が存在する.

$(2)$ $\bar{x} \in \mathbb{Z}/n \mathbb{Z}$ が生成元 $\Longleftrightarrow$ $\mathbb{Z}/n \mathbb{Z}$ での $\bar{x}$ 倍写像が全単射 $\Longleftrightarrow$ $\bar{x} \in \left( \mathbb{Z}/n \mathbb{Z} \right)^{\times}$ $\Longleftrightarrow x, n$ が互いに素.

$(3)$ (中国式剰余定理) $m, n$ が互いに素なら

$\mathbb{Z}/mn \mathbb{Z} \cong \mathbb{Z}/m \mathbb{Z} \times \mathbb{Z}/n \mathbb{Z}$ .

この(命題 3) をふまえると次のことがわかります.

系 4.

$(1)$ $\mathbb{N} \ni n \geq 2$ に対して, $\varphi(n) = \mathbb{Z}/n \mathbb{Z}$ の生成元の個数 $= \vert \left( \mathbb{Z}/n \mathbb{Z} \right)^{\times} \vert$ .

$(2)$ オイラーの $\varphi$ 関数は乗法的関数である. すなわち $m, n \in \mathbb{N}$ が互いに素なら

$\varphi(mn) = \varphi(m) \varphi(n)$ .

$(3)$ $n={p_1}^{e_1} {p_2}^{e_2} \cdots {p_r}^{e_r}$ と素因数分解されたとき

$\displaystyle \varphi(n) = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_r}^{e_r} \prod_{i=1}^{r} \left( 1- \dfrac{1}{p_i} \right) = n \prod_{i=1}^{r} \left( 1- \dfrac{1}{p_i} \right)$ .

系 4.(1) から, $\varphi(n)$ は $\mathbb{Z}/n \mathbb{Z}$ の生成元の個数を表していることと, $p$ を素数として, $\mathbb{F}_p=\mathbb{Z}/p \mathbb{Z}$ が有限体よりその乗法群 $\mathbb{F}_{p}^{\times}=\mathbb{F}_p \setminus \{0\}$ はまた位数 $p-1$ の巡回群, すなわち $\mathbb{Z}/ (p-1) \mathbb{Z}$ と同型になるので次がわかります.

系 5. $p$ を素数とする. このとき

$\varphi( \varphi(p))=\varphi(p-1)= \mathbb{F}_{p}^{\times}$ の生成元の個数.

系 4.(3) と合わせて次がわかります.

系 6. $p$ を素数とする. このとき, $\mathbb{F}_{p}^{\times}$ のうち生成元が占める割合は

$\displaystyle \dfrac{ \varphi(p-1)}{p-1} = \prod_{l} \left( 1- \dfrac{1}{l} \right)$ .

ただしこの積は $p-1$ を割るすべての素数 $l$ をわたる.

ここで次の事実が知られています.

定理 7.(Dirichlet の算術級数定理) $a, n$ を互いに素な自然数とするとき,

$p \equiv a \ {\rm mod} \ n$

となる素数 $p$ が無限に存在する.

命題 8.

$\displaystyle \zeta(1)=\sum_{n=1}^{\infty} \dfrac{1}{n}= \prod_{p} \left( 1- \dfrac{1}{p} \right)^{-1}$ は発散する.

これらを用いて次がわかります.

命題 9. $\mathbb{F}_{p_j}^{\times}$ の生成元の割合が $0$ に収束するような素数の列 $\{ p_j \}$ が存在する.

証明数列 $\{ j \ ! \}_{j=1}^{\infty}$ を考える. このとき

$p_j \equiv 1\ {\rm mod}\ j\ !$

となるような素数 $p_j$ からなる数列 $\{ p_j \}$ を作る. これは Dirichlet の定理より作れる. すると $j\ !$ を割る素数は $p_{j}-1$ も割ることになる. よって

$\displaystyle \dfrac{\varphi(p_{j})}{p_{j}-1} = \prod_{l | (p_{j}-1)} \left( 1- \dfrac{1}{l} \right) \leq \prod_{l | j\ !} \left( 1- \dfrac{1}{l} \right)$