原始根

定義

ある素数 pに対して、 r, r^{2}, r^{3}, \dots, r^{p-1}\ (\mathrm{mod}\ p)が互いに異なるような rのことを pに対する原始根という。例えば、 p=7に対しては

\begin{eqnarray} 3 &\equiv& 3\ (\mathrm{mod}\ 7) \\ 3^{2} &\equiv& 2\ (\mathrm{mod}\ 7) \\ 3^{3} &\equiv& 6\ (\mathrm{mod}\ 7) \\ 3^{4} &\equiv& 4\ (\mathrm{mod}\ 7) \\ 3^{5} &\equiv& 5\ (\mathrm{mod}\ 7) \\ 3^{6} &\equiv& 1\ (\mathrm{mod}\ 7) \\ \end{eqnarray}

となるので3は原始根であるが、

\begin{eqnarray} 2 &\equiv& 2\ (\mathrm{mod}\ 7) \\ 2^{2} &\equiv& 4\ (\mathrm{mod}\ 7) \\ 2^{3} &\equiv& 1\ (\mathrm{mod}\ 7) \\ \end{eqnarray}

となるので2は原子根ではない。

関連する定理

素数に対して原子根は必ず存在する

証明は？

最後の指数の値

フェルマーの小定理より、 r^{p-1} \equiv 1\ (\mathrm{mpd}\ p)なので、原子根の最後の指数のmod値は必ず1である。

類乗ではなく定数倍のmodの種類に関する定理

aと pが互いに素の時、 a, 2a, \dots, (p-1)a\ \mathrm{mod}\ pは互いに異なる。

証明 もし 1 \le m \lt n \le pとなる m, nが存在し maと naのmod pの値が互いに同じであるとする。このとき

\begin{eqnarray} ma &\equiv& na\ (\mathrm{mod}\ p) \\ (n-m)a &\equiv& \ (\mathrm{mod}\ p) \\ \end{eqnarray}

なので (n-m)aは pの倍数である。 aと pは互いに素なので (n-m)が pの倍数でないといけないが、 (n-m) \lt pなので矛盾する。よって題意は示された。

参考

Editorial - AtCoder Beginner Contest 212