整数論の問題

判定法　$p-1=22=2\cdot 11$ の素因数は $q=2,11$ である。$23$ と互いに素な $g$ が原始根であるための必要十分条件は
$$g^{22/2}=g^{11}\not\equiv 1,g^{22/11}=g^2\not\equiv 1(\mathrm{mod}23)$$
の両方が成り立つことである。

理由：$g$ の位数 $d$ は $22$ の約数である。$d<22$ なら、$d$ は $22/2=11$ か $22/11=2$ の少なくとも一方を割り切る。そのため $g^{11}\equiv 1$ または $g^2\equiv 1$ となる。逆に $d=22$ なら、どちらも $1$ にならない。

$g=1,2,3,\dots$ と小さい順に調べる。

- $g=1$：位数は $1$ なので原始根ではない。
- $g=2$：$2^{11}=2048=23\cdot 89+1$ より $2^{11}\equiv 1$。よって原始根ではない。
- $g=3$：$3^3=27\equiv 4$ より $3^6\equiv 16$、$3^9\equiv 16\cdot 4=64\equiv 18$ である。したがって $3^{11}=3^9\cdot 3^2\equiv 18\cdot 9=162=23\cdot 7+1\equiv 1$。よって原始根ではない。
- $g=4$：$4^{11}=2^{22}\equiv 1$（フェルマーの小定理）なので原始根ではない。
- $g=5$：$5^2=25\equiv 2\not\equiv 1$ である。また $5^4\equiv 4$、$5^8\equiv 16$ より
$$5^{11}=5^8\cdot 5^2\cdot 5\equiv 16\cdot 2\cdot 5=160=23\cdot 6+22\equiv -1\not\equiv 1(\mathrm{mod}23).$$

$q=2,11$ のどちらについても $5^{22/q}\not\equiv 1$ なので、$5$ の位数は $22$ であり、$5$ は原始根である。

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

$p=23$ より $p-1=22=2\cdot 11$。したがって位数は $1,2,11,22$ のいずれかである。$g$ が原始根であることは、$g^2\not\equiv 1$ かつ $g^{11}\not\equiv 1(\mathrm{mod}23)$ と同値である。

• $g=1$：位数 $1$。
• $g=2$：$2^{11}=2048=23\cdot 89+1\equiv 1$ なので位数は $11$（原始根でない）。
• $g=3$：平方剰余の記号を計算すると $\left(\frac{3}{23}\right)=-\left(\frac{23}{3}\right)=-\left(\frac{2}{3}\right)=1$。よって $3^{11}\equiv 1$ で、位数は $11$（原始根でない）。直接確かめると $3^3=27\equiv 4$、$3^{11}=3^9\cdot 9=64\cdot 9\equiv 18\cdot 9=162\equiv 1$。
• $g=4=2^2$：$4^{11}=2^{22}\equiv 1$ なので、$4^{11}\not\equiv 1$ を満たさず原始根でない。
• $g=5$：$5^2=25\equiv 2\not\equiv 1$。また $5^{11}$ を計算すると、$5^2\equiv 2$、$5^{10}\equiv 2^5=32\equiv 9$、$5^{11}\equiv 45\equiv -1\not\equiv 1$。よって位数は $22$ で、$5$ は原始根。

したがって最小の原始根は $g=5$。