整数論の問題

判定法の確認

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

(理由) 位数 $d$ は $22$ の約数である。$d<22$ ならば、$d$ は $22/2=11$ または $22/11=2$ のどちらかを割り切る。すると $g^{11}\equiv 1$ または $g^2\equiv 1$ となる。したがって、この 2 つがどちらも $1$ でなければ $d=22$ である。

小さい $g$ から順に調べる

- $g=1$：位数は $1$ なので、原始根ではない。
- $g=2$：$2^{11}=2048=23\cdot 89+1$ より $2^{11}\equiv 1(\mathrm{mod}23)$ となるので、原始根ではない。
- $g=3$：$3^2=9$、$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(\mathrm{mod}23)$（フェルマーの小定理）より、原始根ではない。
- $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 22\equiv -1\not\equiv 1(\mathrm{mod}23)$$
となる。

よって $5$ は $2$ つの条件をどちらもみたし、$23$ を法とする原始根である。

以上より、求める最小の正の原始根は $5$ である。

$p-1=22=2\cdot 11$ なので、$g$ が原始根であるための必要十分条件は $g^2\not\equiv 1$ かつ $g^{11}\not\equiv 1(\mathrm{mod}23)$ である。位数は 22 の約数 1, 2, 11, 22 のいずれかであり、$g^2\equiv 1$ となるのは $g\equiv \pm 1$ のときだけなので、$g\ne 1,22$ なら位数 1, 2 は除かれる。よって $g^{11}\not\equiv 1$（$g$ が平方非剰余）を確かめればよい。

$g=2$: $2^{11}=2048$。$23\cdot 89=2047$ なので $2^{11}\equiv 1(\mathrm{mod}23)$。位数は 11 で原始根ではない。

$g=3$: $3^2=9$, $3^3=27\equiv 4$, $3^6\equiv 16$, $3^9=3^6\cdot 3^3\equiv 16\cdot 4=64\equiv 64-46=18$, $3^{11}=3^9\cdot 9\equiv 18\cdot 9=162=23\cdot 7+1=161+1\equiv 1$。位数は 11 で原始根ではない。

$g=4=2^2$: 2 の位数が 11 なので $4^{11}\equiv 1$。原始根ではない。

$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 45-23=22\equiv -1$。よって $5^{11}\not\equiv 1$、かつ $5^2\equiv 2\not\equiv 1$。したがって位数は 22 である。

検算: $5^{22}=(5^{11}{)}^2\equiv 1$ で、位数は 22 の約数。$5^2\equiv 2\ne 1$, $5^{11}\equiv -1\ne 1$ なので位数 1, 2, 11 ではない。よって位数は 22。

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