原根存在的条件

如果 p 是一个奇素数，则存在模 p 的原根

证明：找到所有数指数的最小公倍数 D，将 D 标准分解：

$$D=q_1^{a_1}{q}_2^{a_2}\dots q_k^{a_k}$$

则其中的某一项 $q^a$ 一定来源于某一个最大的因子，因此一定整除某一个数

$$or{d}_p(x)=n_i=\lambda q_j^{a_j}$$ $$or{d}_p(x^{\lambda })=\frac{\lambda q_j^{a_j}}{(\lambda q_j^{a_j},\lambda )}=q_j^{a_j}$$

---

模 m 的原根存在的充分必要条件是

$$m=2,4,p^a,2p^a$$

p 是奇素数

有限域

---

如何找到原根

即对在简化剩余系里对每个数试 k 次

实际例子：