§A4.12位数と原始根

証明.$d = \operatorname{ord}(a)$とおく。

（$\Leftarrow$）$d \mid n$なら$n = dk$と書け、$a^n = (a^d)^k \equiv 1^k = 1 \pmod m$。

（$\Rightarrow$）$a^n \equiv 1 \pmod m$とする。除法の原理（基礎）より$n = qd + r$，$0 \le r < d$を満たす整数$q, r$がただ一組存在する。このとき

なので、仮定$a^n \equiv 1$と合わせて$a^r \equiv 1 \pmod m$を得る。ここでもし$r > 0$なら、$0 < r < d$を満たす正整数$r$で$a^r \equiv 1$となってしまい、$d$が「$a^k \equiv 1$となる最小の正整数」であることに反する。よって$r = 0$、すなわち$n = qd$で$d \mid n$。▨

証明. オイラーの定理より$a^{\varphi(m)} \equiv 1 \pmod m$なので、命題 1.2を$n = \varphi(m)$に適用すればよい。▨

証明.$d$を$p - 1$の約数とし、$1, 2, \dots, p-1$のうち位数がちょうど$d$であるものの個数を$\psi(d)$と書く。

ステップ 1（総和）.系 1.3より、$1 \le a \le p-1$の位数は必ず$p - 1 = \varphi(p)$の約数なので、

ステップ 2（鍵となる事実）.$\mathbb{Z}/p\mathbb{Z}$は体であり、体上の多項式$x^d - 1$の根は高々$d$個しかない（因数定理より）。したがって合同方程式$x^d \equiv 1 \pmod p$の解は高々$d$個。ここで用いた「根が1つ見つかるたびに1次式で割り切れる」という事実は「数と式の計算」の因数定理であり、それを$\mathbb{Z}/p\mathbb{Z}$の上で使ってよい根拠（剰余類の全体が体になること、および体上の多項式の根の個数が次数を超えないこと）は本記事では認めて用います。環や体の言葉による一般的な扱いは「環と加群」が行います。

ステップ 3（$\psi(d) > 0$なら尽くされる）. もし位数がちょうど$d$の元$a$が1つでもあるとする。$a, a^2, \dots, a^d$の$d$個は互いに相異なる（$a^i \equiv a^j$，$1 \le i < j \le d$とすると$a^{j-i} \equiv 1$となるが$0 < j - i < d$は$d$の最小性に反する）。しかも各$(a^i)^d = (a^d)^i \equiv 1$なので、これら$d$個はすべて$x^d \equiv 1 \pmod p$の解。ステップ 2 より解は高々$d$個しかないから、$a, a^2, \dots, a^d$が解のすべてである。

ステップ 4（位数$d$のものを数える）.$a^i$の位数は$d / \gcd(i, d)$である（一般に巡回する元のべきの位数はこの公式に従う）。これが$d$に等しいのは$\gcd(i, d) = 1$のときで、$1 \le i \le d$の範囲にそのような$i$はちょうど$\varphi(d)$個ある。位数$d$の元はすべてステップ 3 の$d$個の解の中にある（それ自身$x^d \equiv 1$の解だから）ので、

一方$\psi(d) = 0$の場合もある。まとめると、すべての$d \mid p-1$で$\psi(d) \in \{0, \varphi(d)\}$、特に$\psi(d) \le \varphi(d)$。

ステップ 5（等号の強制）. オイラー関数の基本等式（発展レベル）

と、ステップ 1 の$\sum_{d \mid p-1} \psi(d) = p-1$を見比べる。各項で$\psi(d) \le \varphi(d)$なのに総和が完全に一致するので、どの$d \mid p-1$でも$\psi(d) = \varphi(d)$ でなければならない（1つでも$\psi(d) < \varphi(d)$なら左辺の総和が右辺より真に小さくなってしまう）。

特に$d = p - 1$で$\psi(p-1) = \varphi(p-1) \ge 1 > 0$。すなわち位数がちょうど$p-1 = \varphi(p)$の元が存在する——これが原始根である。▨