📂整数論

原始元定理の証明

定義 ¹

$1 \le a \le p$が$\text{ord}_{p} (a) = p-1$を満たす場合、法$p$の原始根と定義される。

---

• 位数$\text{ord}_{p} (a)$は$a^{e} \equiv 1 \pmod{p}$を満たす最小の自然数$e$を意味する。

定理

全ての素数$p$は$\phi ( p - 1)$個の原始根を持つ。

---

• $\phi$はオイラーのφ関数だ。

説明

$\text{ord}_{p} (a) = p-1$を満たす$a$を原始根と呼ぶ理由は、フェルマーの小定理により$a^{p-1} \equiv 1 \pmod{ p }$であるので、正確に$\text{ord}_{p} (a) = p-1$であれば、$a$の累乗で$1$と$p$の間の全ての数を表せるからだ。

例えば$p=7$の原始根$a = 3$を考えると $$\begin{align*} 1 \equiv & 3^{0} \pmod{ 7 } \\ 2 \equiv & 3^{2} \pmod{ 7 } \\ 3 \equiv & 3^{1} \pmod{ 7 } \\ 4 \equiv & 3^{4} \pmod{ 7 } \\ 5 \equiv & 3^{5} \pmod{ 7 } \\ 6 \equiv & 3^{3} \pmod{ 7 } \end{align*}$$

今回は$a$に焦点を当てて$p=7$を考えると $$\begin{align*} 1^{1} \equiv & 1 \pmod{ 7 } \\ 2^{3} \equiv & 1 \pmod{ 7 } \\ 3^{6} \equiv & 1 \pmod{ 7 } \\ 4^{3} \equiv & 1 \pmod{ 7 } \\ 5^{6} \equiv & 1 \pmod{ 7 } \\ 6^{2} \equiv & 1 \pmod{ 7 } \end{align*}$$

ここで$p=7$の原始根は$3,5$二つで、 $$\phi (7-1) = \phi (6) = \phi (3) \phi (2) = (3-1)(2-1) = 2$$ とピッタリ合っていることが確認できる。一方で$\phi ( p - 1)$は少なくとも$1$であるため、正確な数ではなく存在だけを言及するのに使っても構わない。このオイラーのφ関数$\phi$は突然出現したように見えるかもしれないが、証明過程で欠かせない核心要素だ。

証明

Part 1.

位数の性質により、全ての$1 \le a \le (p-1)$に対して、今$(p-1)$を割る全ての約数$d$に対して関数$\psi$を $$\psi ( d ) := \left| \left\{ a \ | \ 1 \le a < p \land \text{ord}_{p} (a) = d \right\} \right|$$ のように定義しよう。Part 4でこの$\psi$がオイラーのφ関数$\phi$と実質的に同じ関数であることを示す。

---

Part 2.

$(p-1)$を割る約数を$n$とし、$(p-1) = nk$であり、$\left( X^{p-1} - 1 \right)$を因数分解すると

$$\begin{align*} X^{p-1} - 1 =& X^{nk} - 1 \\ =& \left( X^{n} \right)^{k} - 1 \\ =& \left( X^{n} - 1 \right) \left( \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \right) \end{align*}$$

である。フェルマーの小定理により、 $$X^{p-1} - 1 \equiv 0 \pmod{p}$$ は$X=1,2,\cdots,(p-1)$を根として持ち、合同方程式に対する代数学の基本定理により、$X^{n} -1 \equiv 0 \pmod{p}$は多くても$n$個の根を持つため、 $$\left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \equiv 0 \pmod{p}$$ は多くても$n(k-1)$個の根を持つ。もう一度 $$X^{p-1} - 1 \equiv \left( X^{n} - 1 \right) \left( \left( X^{n} \right)^{k-1} + \left( X^{n} \right)^{k-2} + \cdots + \left( X^{n} \right)^{2} + \left( X^{n} \right)^{1} + 1 \right) \pmod{p}$$ を考えると

• 左辺には正確に$(p-1) = nk$個の根があり、
• 右辺には多くても$n$個の根と、多くても$n(k-1)$個の根が存在する。

これを満たすためには、$X^{n} -1 \equiv 0 \pmod{p}$は少なくとも$n$個、つまり正確に$n$個の根を持たなければならない。要約すると、$n | (p-1)$の場合、 $$X^{n} -1 \equiv 0 \pmod{p}$$ は$0 \le X < p$で正確に$n$個の解を持つ。

---

Part 3. $\displaystyle \sum_{i=1}^{r} \psi (d_{i}) = n$

$n$の全ての約数を$d_{1} , \cdots , d_{r}$と表示してみよう。

$n$の約数$d$が$d = \text{ord}_{p} (a)$を満たす場合、位数の定義から $$a^{d} = a^{\text{ord}_{p} (a)} \equiv 1 \pmod{p}$$ である。ここで、与えられた$d$に対してこの式を満たす$a$の数は$\psi (d)$となる。

しかし、 $$a^{n} \equiv a^{d \cdot \left( {{n} \over {d}} \right)} \equiv 1^{ \left( {{n} \over {d}} \right)} \equiv 1 \pmod{p}$$ であるため、$\psi (d)$個の$X = a$は$X^{n} -1 \equiv 0 \pmod{p}$の解となる。

整理すると、$X^{n} -1 \equiv 0 \pmod{p}$の解の数は $$\sum_{d \mid n} \psi (d) = \psi (d_{1} ) + \psi (d_{2} ) + \cdots + \psi (d_{r} )$$ となる。上のPart 2で$X^{n} -1 \equiv 0 \pmod{p}$の解の数が$n$だと述べたので、 $$\sum_{d \mid n} \psi (d) = \psi (d_{1} ) + \psi (d_{2} ) + \cdots + \psi (d_{r} ) = n$$ となり、これはオイラーのφ関数の和公式と類似している。

---

Part 4. $\phi (n) = \psi (n)$

全ての自然数$n$に対して$\phi (n) = \psi (n)$が成り立つことを示せばよい。

$\psi$に関する計算は、特に言及がない限り、$\displaystyle \sum_{i=1}^{r} \psi (d_{i}) = n$を用いて得られたものである。

• Case 1. $n=1$
  $\phi (1) = 1$であり$\psi (1) = 1$であるため、$$\phi (1) = \psi (1)$$
• Case 2. 素数$q$に対して$n=q$の場合
  $\phi (q) = q - 1$であり$\psi (q) + \psi (1) = q$であるため、$$\phi (q) = q - 1 = \psi (q)$$
• Case 3. 素数$q$に対して$n=q^2$の場合
  $q^2$の約数は$1, q, q^2$だけであるため、$$\phi (q^2) + \phi (q) + 1 = q^{2} = \psi (q^2) + \psi (q) + 1$$ である。両側からCase 1, 2の結果で項を減じれば、$$\phi (q^2) = \psi (q^2)$$
• Case 4. 異なる素数$q_{1}, q_{2}$に対して$n=q_{1} q_{2}$の場合
  $q_{1} q_{2}$の約数は$1, q_{1}, q_{2}, q_{1} q_{2}$だけであるため、$$\phi ( q_{1} q_{2}) + \phi (q_{1}) + \phi (q_{2}) + 1 = q_{1} q_{2} = \psi ( q_{1} q_{2}) + \psi (q_{1} ) + \psi (q_{2} ) + 1$$ である。両側からCase 1, 2の結果で項を減じれば、$$\phi ( q_{1} q_{2} ) = \psi ( q_{1} q_{2} )$$
• Otherwise.
  他の場合は、Case 3, 4の結果をそのまま項に分ければ、$\phi (n) = \psi (n)$を得る。

---

Part 5.

Part 2, 3で我々は$n | (p-1)$を満たす全ての$n$に対して、$\phi (n)$個の$a$が$\text{ord}_{p} (a) = n$を満たすことを確認した。ここで$k=1$、つまり$n = p-1$である場合、$\text{ord}_{p} (a) = p-1$であるため、$a$は法$p$の原始根になる。したがって、素数$p$は$\phi (p-1)$個の原始根を持つ。

■