整数論の問題

原始根の判定法

$\gcd (g,p)=1$ のとき、$g$ が法 $p$ の原始根であるための条件は次のとおりである。

「$p-1$ のすべての素因数 $q$ について $g^{(p-1)/q}\not\equiv 1(\mathrm{mod}p)$ が成り立つ」

この条件で十分な理由を述べる。位数 ${\mathrm{ord}}_p(g)$ は $p-1$ の約数である。もし位数が $p-1$ より小さい真の約数 $d$ なら、$\frac{p-1}{d}$ はある素因数 $q$ をもち、$d$ は $\frac{p-1}{q}$ を割り切る。すると $g^{(p-1)/q}\equiv 1$ となり、条件に反する。

$p=23$ の場合

$p-1=22=2\cdot 11$ なので、調べる指数は $\frac{22}{2}=11$ と $\frac{22}{11}=2$ の 2 つである。つまり、$g^2\not\equiv 1$ かつ $g^{11}\not\equiv 1(\mathrm{mod}23)$ を確かめればよい。

$g=1$ は位数 $1$ なので原始根ではない。$g=2$ から順に調べる。

• $g=2$：$2^{11}=2048=23\cdot 89+1$ より $2^{11}\equiv 1$ である。よって原始根ではない。
• $g=3$：$3^2=9$、$3^4=81\equiv 12$、$3^8\equiv 144\equiv 6$ である。したがって $3^{11}=3^8\cdot 3^2\cdot 3\equiv 6\cdot 9\cdot 3=162=23\cdot 7+1\equiv 1$ となり、原始根ではない。
• $g=4$：$4^{11}=2^{22}=(2^{11}{)}^2\equiv 1$ より、原始根ではない。
• $g=5$：$5^2=25\equiv 2\not\equiv 1$ である。また $5^{11}=5\cdot (5^2{)}^5\equiv 5\cdot 2^5=160=23\cdot 6+22\equiv -1\not\equiv 1$ である。両方の条件を満たすので、$5$ は原始根である。

よって、求める最小の正の原始根は $g=5$ である。

$22=2\cdot 11$ なので、$g$ が原始根であるための条件は $g^2\not\equiv 1$ かつ $g^{11}\not\equiv 1(\mathrm{mod}23)$ である。$g^{11}$ はオイラーの規準よりルジャンドル記号 $(g/23)$ に等しいので、$g$ が平方非剰余であることが必要。

• $g=1$: 位数 1 なので不適。
• $g=2$: $23\equiv 7(\mathrm{mod}8)$ より $2$ は平方剰余。$2^{11}\equiv 1$ で位数 11。不適。
• $g=3$: $23\equiv -1(\mathrm{mod}12)$ より $3$ は平方剰余。$3^{11}\equiv 1$ で不適。
• $g=4=2^2$: 平方数なので平方剰余。不適。
• $g=5$: $5^2=25\equiv 2$ より $5^{11}=5\cdot (5^2{)}^5\equiv 5\cdot 2^5=5\cdot 32\equiv 5\cdot 9=45\equiv 22\equiv -1(\mathrm{mod}23)$。また $5^2\equiv 2\ne 1$。位数は 22 の約数で、$1,2,11$ のいずれでもないので位数は $22$。

よって最小の原始根は $g=5$。