原根

原根

定义:
设\(m\)是正整数,\(a\)是整数,若\(a\)模\(m\)的阶等于\(\phi(m)\),则称\(a\)为模\(m\)的一个原根。

51nod 1135
求原根。
最小原根求法:
对\(p-1\)分解,从小枚举\(g\)。若\(g^{\frac{p-1}{primeFactor_i}}\)恒成立,则\(g\)为原根。