原始根
$ \bmod p上において、$ p-1乗してはじめて$ 1になるような数を原始根という。
これを「位数が$ p-1」と言うことができる。
たとえば、$ \bmod 17では、$ \{3, 5, 6, 7, 10, 11, 12, 14\}が原始根となる。
原始根でない数、たとえば$ 2についていえば、$ 2^8\equiv 1 \pmod{17}のように、$ p-1以外の何らかの$ p-1の約数で累乗しても$ 1になる。
原始根の個数
これは原始根の位数が$ p-1であるので、どの原始根も$ p-1と互いに素な数乗するとやはり原始根になると考えるとわかりやすい。
これは結構多くて、例えば$ \bmod 998244353だと$ 402653184個あり、半分よりちょっと少ないくらい。
この事実を利用すると、例えば$ 2以上$ p-1以下の数を乱択して原始根判定することで高速に原始根を得ることができる。
原始根判定
事前に$ p-1を素因数分解し、$ p-1の素因数$ P_1, P_2, \ldotsを求めておく。
$ aが原始根かを判定するには、$ \forall i, a^{\frac{p-1}{P_i}} \not\equiv 1 \pmod pであることを判定すればよい。（→位数を求める） $ p-1の素因数の個数より、計算量は$ O(\log p)となる。
原始根の総和
原始根の総和はメビウス関数を使い$ \mu(p-1)と表すことができる。 メビウス関数$ \mu(n)の計算量は$ O(\sqrt n)。
また、$ N以下すべての正整数について求めたいときはエラトステネスの篩と同様な方法で$ O(N \log \log N)で計算できる。
原始根以外の数
任意の原始根$ gおよび正整数$ kに対して、$ g^kの位数は$ \frac{p-1}{\gcd(p-1, k)}となる。
また、$ g, kが与えられていない場合、与えられた数$ xの位数を求める方法については「位数を求める」を参照。 位数が$ m（ただし$ m | p-1）である数は、$ \phi(m)個存在する。
また、それらの総和は$ \mu(m)となる。
総乗は$ (-1)^{\phi(m)}となる。
参考