ある整数\(p\)に対して、整数\(a\)が\(p\)の原始根であるとき、\(a^{n}\)を\(p\)で割った余りが1から\(p-1\)までの全て異なる余りを生成します。このとき、\(n\)は1から\(p-1\)までの範囲を取ります。
例えば、以下の結果から7の原始根は3です。
\[3^{1} \equiv 3 \pmod{7}\]
\[3^{2} \equiv 2 \pmod{7}\]
\[3^{3} \equiv 6 \pmod{7}\]
\[3^{4} \equiv 4 \pmod{7}\]
\[3^{5} \equiv 5 \pmod{7}\]
\[3^{6} \equiv 1 \pmod{7}\]
なお、少なくとも\(p\)が2以上の素数のとき、原始根は存在します。