原根存在的条件

如果 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} = λ q_{j}^{a_{j}}

or d_{p} (x^{λ}) = \frac{λ q _{j}^{a_{j}}}{( λ q _{j}^{a_{j}} , λ )} = q_{j}^{a_{j}}

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

m = 2, 4, p^{a}, 2 p^{a}

p 是奇素数

如何找到原根

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

实际例子：

🪴 Cyril