原根

前置知识

前置：

费马小定理，

欧拉定理，

拉格朗日定理。

这部分知识与抽象代数相关。如果想要进一步了解文中的“阶”、“原根”名字来源，可以参考群论部分。

---

阶

阶：由欧拉定理可知，对 ，，若 ，则 。

因此满足同余式 的最小正整数 存在，这个 称作 模 的阶，记作 。

性质

性质 ： 模 两两不同余。

证明：考虑反证，假设存在两个数 ，且 ，则有 。

但是显然的有：，这与阶的最小性矛盾，故原命题成立。

证毕

---

性质 ：若 ，则 。

证明：对 除以 作带余除法，设 。

若 ，则

这与 的最小性矛盾。故 ，即 。

证毕

据此我还可以推出：

若 ，则有 。

---

还有两个与四则运算有关的重要性质。

性质 ：设 ，，，则

的充分必要条件是

证明：

必要性

由 及 ，可知

由前面所述阶的性质，有

又由于 ，故

即 。

充分性

由 可知

故 。结合 即得

对称地，同理可得

所以

另一方面，有

故

综合以上两点即得

证毕

---

性质 ：设 ，，，，则

证明：注意到：

另一方面，由 ，可知：

故：

综合以上两点，得：

证毕

---

原根

原根：设 ，。若 ，且 ，则称 为模 的原根。

满足 ，对于质数 ，也就是说 结果互不相同。

原根判定定理

原根判定定理：设 ，则 是模 的原根的充要条件是，对于 的每个素因数 ，都有 。

证明： 必要性显然，下面用反证法证明充分性。

当对于 的每个素因数 ，都有 成立时，我们假设存在一个 ，其不是模 的原根。

因为 不是 的原根，则存在一个 使得 。

由

裴蜀定理 得，一定存在一组 满足 。

又由

欧拉定理 得 ，故有：

由于 且 。

故存在 的素因数 使得 。

则 ，与条件矛盾。

故假设不成立，原命题成立。

证毕

原根个数

若一个数 有原根，则它原根的个数为 。

证明：若 有原根 ，则：

所以若 ，则有：，即 也是模 的原根。

而满足 且 的 有 个。所以原根就有 个。

证毕

原根存在定理

原根存在定理：一个数 存在原根当且仅当 ，其中 为奇素数，。

模 有原根的充要条件 :。

我们来证明它，分成 、、 与 ，四个部分。

• ，原根显然存在。

• ，其中 为奇素数，。

  定理 1：对于奇素数 ， 有原根。

  证明：先证一个引理：

  引理：设 与 是与 互素的两个整数，则存在 使得 。

  证明：我们先将 表示成质因数分解的形式：

  接着将它们表示成如下形式：

  其中：

  则由阶的 性质 ，可得：

  同理：

  又因为显然有 ，，则再由阶的 性质 ，可得：

  于是令 则原命题得证。

  证毕

  回到原命题，对 依次两两使用引理，可知存在 使得

  这表明 ，所以 都是同余方程

  的根。由拉格朗日定理，可知方程的次数 。

  又由费马小定理，易知 ，故 。

  综上可知 为模 的原根。

  证毕

  ---

  定理 2：对于奇素数 ，， 有原根。

  证明：一个基本的想法是将模 的原根平移。

  先证明一个引理：

  引理：存在模 的原根 ，使得 。

  证明：事实上，任取模 的原根 ，若 不满足条件，我们认定 满足条件。

  易知 也是模 的原根。

  我们有

  证毕

  回到原题，我们证明若 是一个满足引理条件的原根，则对任意 ， 是模 的原根。

  首先，证明下面的结论：对任意 ，都可设

  这里 。事实上， 时，由 的选取可知结论成立。现设上式对 时成立，则

  结合 可知命题对 成立。

  所以命题对任意 都成立。

  其次，记 ，则由欧拉定理，可知 。

  而由 为模 的原根，及 。

  所以可设 ，这里 。

  现在利用之前的结论，可知：

  结合 可知 。

  综上可知，，即：

  从而， 是模 的原根。

  证毕

• ，其中 为奇素数，。

  定理 ：对于奇素数 ，， 的原根存在。

  证明：设 是模 的原根，则 也是模 的原根。

  在 和 中有一个是奇数，设这个奇数是 ，则 。

  由欧拉定理，。

  而 ，故：

  利用 为模 的原根可知 。

  结合 可知 为模 的原根。

  证毕

• ，其中 为奇素数，。

  定理 ：对于 ，且不存在奇素数 及 使得 ，模 的原根不存在。

  证明：对于 ，，则对任意奇数 均有：

  其中最后一步用到 与 同奇偶，故其和为偶数。

  若 不是 的幂，且 为符合题目条件的数，则可设 ，这里 且 。

  此时，若 ，由欧拉定理可知：

  注意到 时， 为偶数，所以：

  进而：

  由原根定义可得：模 的原根不存在。

  证毕

---

综合以上 个定理，我们便给出了一个数存在原根的充要条件。

最小原根的数量级

王元于 年证明了若 有原根，其最小原根是不多于 级别的。此处略去证明。

这保证了我们暴力找一个数的最小原根，复杂度是可以接受的。