原根

前置知识

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

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


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

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

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

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

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

性质

性质 两两不同余。

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

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

证毕


性质 :若 ,则

证明:对 除以 作带余除法,设

,则

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

证毕

据此我还可以推出:

,则有


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

性质 :设 ,则

的充分必要条件是

证明

必要性

,可知

由前面所述阶的性质,有

又由于 ,故

充分性

可知

。结合 即得

对称地,同理可得

所以

另一方面,有

综合以上两点即得

证毕


性质 :设 ,则

证明:注意到:

另一方面,由 ,可知:

故:

综合以上两点,得:

证毕


原根

原根:设 。若 ,且 ,则称 为模 的原根。

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

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

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

原根判定定理

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

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

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

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

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

又由 欧拉定理,故有:

由于

故存在 的素因数 使得

,与条件矛盾。

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

证毕

原根个数

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

证明:若 有原根 ,则:

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

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

证毕

原根存在定理

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

有原根的充要条件 :

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

  • ,原根显然存在。

  • ,其中 为奇素数,

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

    证明:先证一个引理:

    引理:设 是与 互素的两个整数,则存在 使得

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

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

    其中:

    则由阶的 性质 ,可得:

    同理:

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

    于是令 则原命题得证。

    证毕

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

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

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

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

    综上可知 为模 的原根。

    证毕


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

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

    先证明一个引理:

    引理:存在模 的原根 ,使得

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

    易知 也是模 的原根。

    我们有

    证毕

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

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

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

    结合 可知命题对 成立。

    所以命题对任意 都成立。

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

    而由 为模 的原根,及

    所以可设 ,这里

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

    结合 可知

    综上可知,,即:

    从而, 是模 的原根。

    证毕

  • ,其中 为奇素数,

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

    证明:设 是模 的原根,则 也是模 的原根。

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

    由欧拉定理,

    ,故:

    利用 为模 的原根可知

    结合 可知 为模 的原根。

    证毕

  • ,其中 为奇素数,

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

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

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

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

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

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

    进而:

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

    证毕


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

最小原根的数量级

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

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