阶
阶的定义：当 \(\gcd(a,m)=1\) 时 \(a^{\varphi(m)}\equiv1\pmod m\) 若 \(a^{k}\equiv1\pmod m\) 则 \(k_{min}\) 为阶 \(k=\operatorname{ord}_m(a)\)。
显然有 \(\operatorname{ord}_m(a)\mid \varphi(m)\) 然后我们就可以通过质因数分解之类的来 \(O(\log_2a)\) 做了
原根
原根就是在阶的基础上 \(\operatorname{ord}_m(a)=\varphi(m)\) 的 \(a\) 就是原根。
当 \(m=1,2,4,p^a,2p^a\) 其中 \(p\) 是奇素数。
求原根没有什么好的办法直接暴力求，问题怎么判断是不是原根，同求阶的方法就行。
性质：当 \(m\) 为质数时，\(\{g^0,g^1,...,g^{m-2}\}\) 为 \(1\sim m-1\) 的排列
例题 \(1\)：P6091