跳转至

原根

前置知识

前置:费马小定理欧拉定理拉格朗日定理

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

定义

由欧拉定理可知,对 ,若 ,则 .

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

在抽象代数中,这里的「阶」就是模 缩剩余系关于乘法形成的群中,元素 的阶。记号 表示阶也只用于这个特殊的群。

下面的诸多性质可以直接扩展到抽象代数中阶的性质。

另外还有「半阶」的概念,在数论中会出现 记号,表示同余式 的最小正整数。半阶不是群论中的概念。阶一定存在,半阶不一定存在。

性质

性质 1

两两不同余。

证明

考虑反证,假设存在两个数 ,且 ,则有 .

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

性质 2

,则 .

证明

除以 作带余除法,设 .

,则

这与 的最小性矛盾。故 ,即 .

据此还可推出:

,则有 .

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

性质 3

,则

的充分必要条件是

证明
  • 必要性:由 ,可知

    由前面所述阶的性质,有

    又由于 ,故

    .

  • 充分性:由 可知

    . 结合 即得

    对称地,同理可得

    所以

    另一方面,有

    综合以上两点即得

性质 4

,则

证明

注意到:

另一方面,由 ,可知:

故:

综合以上两点,得:

原根

定义

. 若 ,且 ,则称 为模 的原根。

满足 . 当 是质数时,我们有 的结果互不相同。

在抽象代数中,原根就是循环群的生成元。这个概念只在模 缩剩余系关于乘法形成的群中有「原根」这个名字,在一般的循环群中都称作「生成元」。

并非每个模 缩剩余系关于乘法形成的群都是循环群,存在原根就表明它同构于循环群,如果不存在原根就表明不同构。

原根判定定理

,则 是模 的原根的充要条件是,对于 的每个素因数 ,都有 .

证明

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

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

因为 不是 的原根,则存在一个 使得 .

裴蜀定理 得,一定存在一组 满足 .

又由 欧拉定理,故有:

由于 .

故存在 的素因数 使得 .

,与条件矛盾。

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

原根个数

若一个数 有原根,则它原根的个数为 .

证明

有原根 ,则:

所以若 ,则有:,即 也是模 的原根。

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

原根存在定理

原根存在定理

一个数 存在原根当且仅当 ,其中 为奇素数,.

我们来证明它,分成 ,四个部分。

  1. ,原根显然存在。

  2. ,其中 为奇素数,.

    定理 1

    对于奇素数 有原根。

    证明

    先证一个引理:

    是与 互素的两个整数,则存在 使得 .

    证明

    我们先将 表示成质因数分解的形式:

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

    其中:

    则由阶的 性质 4,可得:

    同理:

    又因为显然有 ,则再由阶的 性质 3,可得:

    于是令 则原命题得证。

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

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

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

    又由费马小定理,易知 ,故 .

    综上可知 为模 的原根。

    定理 2

    对于奇素数 有原根。

    证明

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

    先证明一个引理:

    存在模 的原根 ,使得 .

    证明

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

    易知 也是模 的原根。

    我们有

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

    首先,证明下面的结论:对任意 ,都可设

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

    结合 可知命题对 成立。

    所以命题对任意 都成立。

    其次,记 ,则由欧拉定理,可知 .

    而由 为模 的原根,及 .

    所以可设 ,这里 .

    现在利用之前的结论,可知:

    结合 可知 .

    综上可知,,即:

    从而, 是模 的原根。

  3. ,其中 为奇素数,.

    定理 3

    对于奇素数 的原根存在。

    证明

    是模 的原根,则 也是模 的原根。

    中有一个是奇数,设这个奇数是 ,则 .

    由欧拉定理,.

    ,故:

    利用 为模 的原根可知 .

    结合 可知 为模 的原根。

  4. ,其中 为奇素数,.

    定理 4

    对于 ,且不存在奇素数 使得 ,模 的原根不存在。

    证明

    对于 ,则对任意奇数 均有:

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

    不是 的幂,且 为符合题目条件的数,则可设 ,这里 .

    此时,若 ,由欧拉定理可知:

    注意到 时, 为偶数,所以:

    进而:

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

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

最小原根的范围估计

王元2和 Burgess1证明了素数 的最小原根 ,其中 .

Fridlander3和 Salié4证明了素数 的最小原根 .

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

参考资料与注释

  1. Primitive root modulo n - Wikipedia

  1. BURGESS, David A. On character sums and primitive roots.Proceedings of the London Mathematical Society, 1962, 3.1: 179-192. 

  2. Wang Y. On the least primitive root of a prime (in Chinese).Acta Math Sinica, 1959, 4: 432–441; English transl. inSci. Sinica, 1961, 10: 1–14 

  3. FRIDLENDER, V. R. On the least n-th power non-residue. In:Dokl. Akad. Nauk SSSR. 1949. p. 351-352. 

  4. SALIÉ, Hans. Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl.Mathematische Nachrichten, 1949, 3.1: 7-8.