原始根と指数

$p$ を法とする剰余系のうち、$p$ を法とする位数が $d$ のものが存在するとして、そのひとつを $a$ とすると $x=a^k (k=0, 1, \ldots, d-1)$ は互いに不合同でかつ
$$\label{eq1}x^d-1\equiv 0\Mod{p}\tag{1}$$
の解である。

前ページの定理3 より \eqref{eq1} の互いに不合同な解の個数は $d$ 個以下だから、
$$x^d-1\equiv 0\Mod{p}\Longleftrightarrow x\equiv a^k\Mod{p}$$
となることがわかる。

また $\gcd(k, d)=k_1>1$ のとき
$$(a^k)^{d/\gcd(k, d)}\equiv (a^d)^{k/\gcd(k, d)}\equiv 1\Mod{p}$$
より、$p$ を法とする $a^k$ の位数は $d/\gcd(k, d)$ の約数なので $d$ より小さい。

このことから、$p$ を法とする $b$ の位数が $d$ ならば
$b\equiv a^k\Mod{p}, \gcd(k, d)=1$
とならなければならない。逆に $b$ がこのような形のとき、
$$b^g\equiv 1\Mod{p}\Longleftrightarrow d\mid kg\Longleftrightarrow d\mid g$$
より、$p$ を法とする $b$ の位数は $d$ に一致する。
よって $p$ を法とする剰余系のうち、$p$ を法とする位数が $d$ に一致するものが存在すれば、それらの個数は $\varphi(d)$ に一致する。

$d$ の約数に対して
$$S_d=\{k(n/d): 0\leq k\leq d-1, \gcd(k, d)=1\}$$
と定義すると $\# S_d=\varphi(d)$ となる。

また、$0\leq m\leq n-1$ となる整数 $m$ に対して $d=n/\gcd(m, n)$, $k=m/\gcd{m, n}$ とおくと
$$m=k\gcd(m, n)=kn/d\in S_d$$
となるから、$0\leq m\leq n-1$ となる整数 $m$ は $S_{n/\gcd(m, n)}$ に属する。

一方、$m\in S_d$ ならば $m=kn/d$ とおくと $n/d$ は $m, n$ の公約数なので、 $m, n$ の最大公約数は $n/d$ の倍数でなければならない。しかし、 $\gcd(m, n)=fn/d$ とおくと $f$ は $m/(n/d)=k$ と $n/(n/d)=d$ の公約数なので $f=1$ つまり $\gcd(m, n)=n/d$ あるいは $d=n/\gcd(m, n)$ となる。
よって $0\leq m\leq n-1$ となる整数 $m$ は $S_{n/\gcd(m, n)}$ にのみ属するので、
$$n=\sum_{d\mid n} \# S_d=\sum_{d\mid n}\varphi(d)$$
が成り立つ。

$1, 2, \ldots, p-1$ のうち、$p$ を法とする位数が $d$ のものの個数を $a_d$ とおくと 命題1 より $a_d\leq \varphi(d)$ となる。
一方、$p$ を法とする位数は $p-1$ の約数だから
$$p-1\leq \sum_{d\mid p-1} a_d$$
となる。$a_d<\varphi(d)$ となる $d$ があるとすれば、 定理2 より
$$p-1<\sum_{d\mid p-1} \varphi(d)=p-1$$
となって矛盾する。よって、$p-1$ のどの約数 $d$ に対しても $a_d=\varphi(d)$ が成り立つ。

整数 $1, \ldots, p-1$ からひとつ整数 $a$ をとり、その $p$ を法とする位数を $s$ とおく。
$s=p-1$ のとき $a$ は $p$ を法とする原始根。
$s< p-1$ のとき
$$x^s-1\equiv 0\Mod{p}, 1\leq x\leq p-1$$
となる整数 $x$ の個数は $s$ 以下なので、$p-1$ より少ない。よって
$$b^s\not\equiv 1\Mod{p}, 1\leq b\leq p-1$$
となる整数 $b$ がとれる。$b$ の $p$ を法とする位数を $t$ とおくと、$t$ は $s$ を割り切らない。

$$s=p_1^{e_1} p_2^{e_2} \cdots, p_k^{e_k}, t=p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}$$
と素因数分解し、$u=\prod_{e_i\geq f_i}p_i^{e_i}, v=\prod_{e_i< f_i} p_i^{f_i}$ とおくと
$u\mid s, v\mid t, \gcd(u, v)=1$ かつ
$$uv=\prod_{i=1}^k p_i^{\max\{e_i, f_i\}}=\LCM[s, t]$$
が成り立つ。
$a_1=a^{s/u}, b_1=b^{t/v}$ とおくと $a_1, b_1$ の $p$ を法とする位数はそれぞれ $u, v$ である。

$p$ を法とする $a_1 b_1$ の位数を $k$ とすると、
$$b_1^{ku}\equiv (a_1 b_1)^{ku}\equiv 1\Mod{p}$$
より $v\mid ku$ だが $\gcd(u, v)=1$ より $v\mid k$ となる。
同様に
$$a_1^{kv}\equiv (a_1 b_1)^{kv}\equiv 1\Mod{p}$$
より $u\mid kv$ だが $\gcd(u, v)=1$ より $u\mid k$ となる。
よって $k$ は $u, v$ 両方で割り切れるから $\LCM[u, v]=uv=\LCM[s, t]$ で割り切れる。
$t$ は $s$ を割り切らないので
$$k\geq \LCM[s, t]>s$$
となり、$a_1 b_1$ の位数は $s$ より大きい。
$a$ のかわりに $a_1 b_1$ をとり、同様の議論を繰り返すと、位数は次第に増加していくから、最終的に原始根を得る。

1. $\ind_a m\equiv g\Mod{p-1}, \ind_a n\equiv h\Mod{p-1}$ ならば
   $m\equiv a^g\Mod{p}, n\equiv a^h\Mod{p}$ なので $mn\equiv a^{g+h}\Mod{p}$ つまり $\ind_a (mn)\equiv g+h\Mod{p-1}$.
2. $\ind_a b\equiv g\Mod{p-1}, \ind_b c\equiv h\Mod{p-1}$ ならば
   $b\equiv a^g\Mod{p}, c\equiv b^h\Mod{p}$ なので $c\equiv (a^g)^h\equiv a^{gh} \Mod{p}$ つまり $\ind_a c\equiv gh\Mod{p-1}$.