原根与阶

前置知识

欧拉定理

原理知识

阶

定义

设a，p是整数，a 和 p 互素，那么：使 $a^n \equiv 1 \;(mod\;p)$ 成立的最小正整数 n 叫做 a 模 p 的阶，记作 $ord_p a$。

性质

1. $ord_p a|\;φ(p)$
2. $a,a^2,a^3,\ldots,a^φ(p)$,在模 p 意义下互不相等
3. $a^r≡a^{r′}(mod\;p)⇔r≡r′(mod\;ord_p^a)$

求解

枚举 $ord_p a$ 的质因子，进行试除法即可。