欧拉定理
若$a,p\;\in\;N^{+},(a,p)=1$,则$a^\phi(p)\;\equiv\;1(mod\;p)$.
阶
使得$a^x\;\equiv\;1(mod\;p)$的最小正整数$x$称为$a$模$p$的阶,记为$ord_pa$.
- 实现
找一个数的阶可以暴力求解,原根为$\phi(p)$的因数.
- 例题
yayamao的神题.
原根
原根:$ord_pa=\phi(p)$时,称$a$是$p$的原根.
$a^1,a^2,...,a^{\phi(p)}$在模p意义下互不相同.
如果$p$有原根,那么原根个数为$\phi(phi(p))$.