原根存在性定理 首先理解基本定义：一个正整数 \(m\) 的原根，是指模 \(m\) 的一个剩余类 \(g\)，满足 \(g\) 模 \(m\) 的乘法阶恰好等于 \(\varphi(m)\)，这里 \(\varphi\) 是欧拉函数。这意味着集合 \(\{g^1, g^2, \dots, g^{\varphi(m)}\}\) 模 \(m\) 两两不同余，恰好构成模 \(m\) 的简化剩余系。 接下来，我们需要判断哪些模数 \(m\) 存在原根。这是一个经典的数论问题，结论由高斯等数学家证明，即原根存在性定理。 第一步：考虑模数是奇素数幂的情况，即 \(p^k\)，其中 \(p\) 是奇素数，\(k\) 是正整数。 模奇素数 \(p\) ：可以证明，任何奇素数 \(p\) 都有原根。证明思路通常涉及分析多项式 \(x^d \equiv 1 \pmod{p}\) 的解数不超过 \(d\)，再结合欧拉函数求和公式 \(\sum_ {d|\varphi(p)} \varphi(d) = \varphi(p)\)。通过计数论证可以推出，至少存在一个模 \(p\) 的原根。 模奇素数的幂 \(p^k\) (\(k \ge 2\)) ：从模 \(p\) 的原根出发，可以“提升”到模 \(p^k\)。具体地，如果 \(g\) 是模 \(p\) 的一个原根，那么 \(g\) 或 \(g+p\) 中至少有一个是模 \(p^2\) 的原根。进一步，如果一个整数 \(g\) 是模 \(p^2\) 的原根，那么它自动是模所有 \(p^k\) (\(k \ge 2\)) 的原根。这个提升过程的关键在于分析指数在模幂下的阶如何变化。 第二步：考虑模数是 2 的幂的情况，即 \(2^k\)。 模 2 和模 4 ：模 2 的原根是 1（平凡情况）。模 4 的原根是 3，因为 3 的阶是 \(\varphi(4)=2\)。 模 \(2^k\) 当 \(k \ge 3\) ：这时没有原根。原因在于，对于任意与 2 互质的奇数 \(a\)，可以证明 \(a^{2^{k-2}} \equiv 1 \pmod{2^k}\)，而 \(\varphi(2^k) = 2^{k-1}\)。因此，任何奇数的阶最多是 \(2^{k-2}\)，无法达到 \(2^{k-1}\)，所以不存在原根。不过，此时简化剩余系的结构是循环群与二阶群的直积，存在一个生成元组。 第三步：考虑一般的模数 \(m\)。根据中国剩余定理，模 \(m\) 的简化剩余系同构于其素幂因子模的简化剩余系的直积。要使这个直积是循环群（即存在一个单一的原根生成整个群），必须要求每个直积分量都是循环群，且这些循环群的阶两两互质。 由前述，奇素数幂 \(p^k\) 的简化剩余系是循环群。 模 \(2^k\) 的简化剩余系在 \(k=1,2\) 时是循环群，在 \(k\ge3\) 时是 \(C_ 2 \times C_ {2^{k-2}}\) 型（非循环）。 因此，要使得直积是循环群，模数 \(m\) 必须能写成以下形式之一： \(m = 1, 2, 4\)。 \(m = p^k\)，其中 \(p\) 是奇素数。 \(m = 2p^k\)，其中 \(p\) 是奇素数。 在 \(m=2p^k\) 的情况下，因为 \(\varphi(2)=1\) 和 \(\varphi(p^k)\) 互质，所以其简化剩余系仍是循环群。 最终，我们将原根存在性定理完整表述为： 定理 ：正整数 \(m\) 存在原根，当且仅当 \(m\) 是下列数之一：\(1, 2, 4, p^k, 2p^k\)，其中 \(p\) 是奇素数，\(k\) 是任意正整数。