原根

前置知识

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

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


:由欧拉定理可知,对 a\in \mathbb{Z} m\in\mathbb{N}^{*} ,若 \gcd(a,m)=1 ,则 a^{\varphi(m)}\equiv 1\pmod m

因此满足同余式 a^n \equiv 1 \pmod m 的最小正整数 n 存在,这个 n 称作 a m 的阶,记作 \delta_m(a)

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

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

另外还有“半阶”的概念,在数论中会出现 \delta^- 记号,表示同余式 a^n \equiv -1 \pmod m 的最小正整数。半阶不是群论中的概念。阶一定存在,半阶不一定存在。

性质

性质 1 a,a^2,\cdots,a^{\delta_m(a)} m 两两不同余。

证明:考虑反证,假设存在两个数 i\ne j ,且 a^i\equiv a^j\pmod m ,则有 a^{|i-j|}\equiv 1\pmod p

但是显然的有: 0<|i-j|<\delta_m(a) ,这与阶的最小性矛盾,故原命题成立。

证毕


性质 2 :若 a^n \equiv 1 \pmod m ,则 \delta_m(a)\mid n

证明:对 n 除以 \delta_m(a) 作带余除法,设 n=\delta_m(a)q+r,0\leq r<\delta_m(a)

r>0 ,则

a^r\equiv a^r(a^{\delta_m(a)})^q\equiv a^n \equiv 1 \pmod m

这与 \delta_m(a) 的最小性矛盾。故 r=0 ,即 \delta_m(a)\mid n

证毕

据此我还可以推出:

a^p\equiv a^q\pmod m ,则有 p\equiv q\pmod{\delta_m(a)}


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

性质 3 :设 m\in\mathbb{N}^{*} a,b\in\mathbb{Z} \gcd(a,m)=\gcd(b,m)=1 ,则

\delta_m(ab)=\delta_m(a)\delta_m(b)

的充分必要条件是

\gcd\big(\delta_m(a),\delta_m(b)\big)=1

证明

必要性

a^{\delta_m(a)}\equiv 1 \pmod m b^{\delta_m(b)} \equiv 1 \pmod m ,可知

(ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1 \pmod m

由前面所述阶的性质,有

\delta_m(ab)\mid\operatorname{lcm}\big(\delta_m(a),\delta_m(b)\big)

又由于 \delta_m(ab)=\delta_m(a)\delta_m(b) ,故

\delta_m(a)\delta_m(b)\mid\operatorname{lcm}\big(\delta_m(a),\delta_m(b)\big)

\gcd(\delta_m(a),\delta_m(b))=1

充分性

(ab)^{\delta_m(ab)}\equiv 1 \pmod m 可知

1 \equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)\delta_m(b)} \pmod m

\delta_m(a)\mid\delta_m(ab)\delta_m(b) 。结合 \gcd(\delta_m(a),\delta_m(b))=1 即得

\delta_m(a)\mid\delta_m(ab)

对称地,同理可得

\delta_m(b)\mid\delta_m(ab)

所以

\delta_m(a)\delta_m(b)\mid\delta_m(ab)

另一方面,有

(ab)^{\delta_m(a)\delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1 \pmod m

\delta_m(ab)\mid\delta_m(a)\delta_m(b)

综合以上两点即得

\delta_m(ab)=\delta_m(a)\delta_m(b)

证毕


性质 4 :设 k \in \mathbb{N} m\in \mathbb{N}^{*} a\in\mathbb{Z} \gcd(a,m)=1 ,则

\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd\big(\delta_m(a),k\big)}

证明:注意到:

a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1 \pmod m
\Rightarrow \delta_m(a)\mid k\delta_m(a^k)
\Rightarrow \dfrac{\delta_m(a)}{\gcd\big(\delta_m(a),k\big)}\mid\delta_m(a^k)

另一方面,由 a^{\delta_m(a)}\equiv 1 \pmod m ,可知:

(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}}\equiv 1 \pmod m

故:

\delta_m(a^k)\mid\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}

综合以上两点,得:

\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}

证毕


原根

原根:设 m \in \mathbb{N}^{*} a\in \mathbb{Z} 。若 \gcd(a,m)=1 ,且 \delta_m(a)=\varphi(m) ,则称 a 为模 m 的原根。

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

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

原根判定定理

原根判定定理:设 m \geqslant 3, \gcd(a,m)=1 ,则 a 是模 m 的原根的充要条件是,对于 \varphi(m) 的每个素因数 p ,都有 a^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m

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

当对于 \varphi(m) 的每个素因数 p ,都有 a^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod m 成立时,我们假设存在一个 a ,其不是模 m 的原根。

因为 a 不是 m 的原根,则存在一个 t<\varphi(m) 使得 a^t\equiv 1\pmod{m}

裴蜀定理 得,一定存在一组 k,x 满足 kt=x\varphi(m)+\gcd(t,\varphi(m))

又由 欧拉定理 a^{\varphi(m)}\equiv 1\pmod{m} ,故有:

1\equiv a^{kt}\equiv a^{x\varphi(m)+\gcd(t,\varphi(m))}\equiv a^{\gcd(t,\varphi(m))}\pmod{m}

由于 \gcd(t, \varphi(m)) \mid \varphi(m) \gcd(t, \varphi(m))\leqslant t < \varphi(m)

故存在 \varphi(m) 的素因数 p 使得 \gcd(t, \varphi(m)) \mid \frac{\varphi(m)}{p}

a^{\frac{\varphi(m)}{p}}\equiv a^{(t, \varphi(m))}\equiv 1\pmod{m} ,与条件矛盾。

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

证毕

原根个数

若一个数 m 有原根,则它原根的个数为 \varphi(\varphi(m))

证明:若 m 有原根 g ,则:

\delta_m(g^k)=\dfrac{\delta_m(g)}{\gcd\big(\delta_m(g),k\big)}=\dfrac{\varphi(m)}{\gcd\big(\varphi(m),k\big)}

所以若 \gcd\big(k,\varphi(m)\big)=1 ,则有: \delta_m(g^k)=\varphi(m) ,即 g^k 也是模 m 的原根。

而满足 \gcd\big(\varphi(m),k\big)=1 1\leq k \leq \varphi(m) k \varphi(\varphi(m)) 个。所以原根就有 \varphi(\varphi(m)) 个。

证毕

原根存在定理

原根存在定理:一个数 m 存在原根当且仅当 m=2,4,p^{\alpha},2p^{\alpha} ,其中 p 为奇素数, \alpha\in \mathbb{N}^{*}

我们来证明它,分成 m=2,4 m=p^{\alpha} m=2p^{\alpha} m\ne 2,4,p,p^{\alpha} ,四个部分。

  • m=2,4 ,原根显然存在。

  • m=p^{\alpha} ,其中 p 为奇素数, \alpha\in \mathbb{N}^*

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

    证明:先证一个引理:

    引理:设 a b 是与 p 互素的两个整数,则存在 c\in\mathbb{Z} 使得 \delta_p(c)=\operatorname{lcm}\big(\delta_p(a),\delta_p(b)\big)

    证明:我们先将 \delta_m(a),\delta_m(b) 表示成质因数分解的形式:

    \left(\delta_m(a)=\prod_{i=1}^k{p_i^{\alpha_i}},\delta_m(b)=\prod_{i=1}^k{p_i^{\beta_i}} \right)

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

    \delta_m(a)=XY,\delta_m(b)=ZW

    其中:

    Y=\prod_{i=1}^k{p_i^{[\alpha_i>\beta_i]\alpha_i}},X=\dfrac {\delta_m(a)}Y
    W=\prod_{i=1}^k{p_i^{[\alpha_i\le\beta_i]\beta_i}},Z=\dfrac {\delta_m(b)}W

    则由阶的 性质 4 ,可得:

    \delta_m\left(a^X\right)=\dfrac{\delta_m(a)}{\gcd\big(\delta_m(a),X\big)}=\dfrac {XY}X=Y

    同理:

    \delta_m\left(b^Z\right)=W

    又因为显然有 \gcd(Y,W)=1 YW=\operatorname{lcm}\big(\delta_p(a),\delta_p(b)\big) ,则再由阶的 性质 1 ,可得:

    \delta_m\left(a^Xb^Z\right)=\delta_m\left(a^X\right)\delta_m\left(b^Z\right)=YW=\operatorname{lcm}\big(\delta_p(a),\delta_p(b)\big)

    于是令 c=a^Xb^Z 则原命题得证。

    证毕

    回到原命题,对 1 \sim (p-1) 依次两两使用引理,可知存在 g\in \mathbb{Z} 使得

    \delta_p(g)=\operatorname{lcm}\big(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\big)

    这表明 \delta_p(j)\mid\delta_p(g)(j=1,2,\cdots,p-1) ,所以 j=1,2,\cdots,p-1 都是同余方程

    x^{\delta_p(g)}\equiv 1\pmod p

    的根。由拉格朗日定理,可知方程的次数 \delta_p(g) \geq p-1

    又由费马小定理,易知 \delta_p(g) \leq p-1 ,故 \delta_p(g)=p-1=\varphi(p)

    综上可知 g 为模 p 的原根。

    证毕


    定理 2:对于奇素数 p \alpha \in \mathbb{N}^{*} p^\alpha 有原根。

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

    先证明一个引理:

    引理:存在模 p 的原根 g ,使得 g^{p-1}\not\equiv 1 \pmod {p^2}

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

    易知 g+p 也是模 p 的原根。

    我们有

    \begin{aligned}(g+p)^{p-1}&\equiv C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2}\\&\equiv g^{p-1}+p(p-1)g^{p-2}\\&\equiv 1-pg^{p-2}\\&\not\equiv 1 \pmod {p^2}\end{aligned}

    证毕

    回到原题,我们证明若 g 是一个满足引理条件的原根,则对任意 \alpha\in\mathbb{N}^{*} g 是模 p^{\alpha} 的原根。

    首先,证明下面的结论:对任意 \beta\in\mathbb{N}^{*} ,都可设

    g^{\varphi(p^\beta)}=1+p^{\beta}\times k_{\beta}

    这里 p\nmid k_{\beta} 。事实上, \beta=1 时,由 g 的选取可知结论成立。现设上式对 \beta 时成立,则

    \begin{aligned}g^{\varphi(p^{\beta+1})}&=(g^{\varphi(p^{\beta})})^{p}\\&=(1+p^{\beta}\times k_{\beta})^p\\&\equiv 1+p^{\beta+1}\times k_{\beta} \pmod {p^{\beta+2}}\end{aligned}

    结合 p\nmid k_{\beta} 可知命题对 \beta+1 成立。

    所以命题对任意 \beta\in\mathbf{N}^{*} 都成立。

    其次,记 \delta=\delta_{p^\alpha}(g) ,则由欧拉定理,可知 \delta\mid p^{\alpha-1}(p-1)

    而由 g 为模 p 的原根,及 g^{\delta}\equiv 1\pmod {p^\alpha}

    所以可设 \delta=p^{\beta-1}(p-1) ,这里 1\leq \beta\leq \alpha

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

    g^{\varphi(p^{\beta})}\not\equiv 1\pmod {p^{\beta+1}}\Rightarrow g^{\delta}\not\equiv 1\pmod {p^{\beta+1}}

    结合 g^{\delta}\equiv 1\pmod {p^\alpha} 可知 \beta \geq \alpha

    综上可知, \beta=\alpha ,即:

    \delta_{p^{\alpha}}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha)

    从而, g 是模 p^{\alpha} 的原根。

    证毕

  • m=2p^{\alpha} ,其中 p 为奇素数, \alpha\in\mathbb{N}^*

    定理 3 :对于奇素数 p \alpha\in\mathbf{N}^{*} 2p^{\alpha}2 的原根存在。

    证明:设 g 是模 p^{\alpha} 的原根,则 g+p^{\alpha} 也是模 p^{\alpha} 的原根。

    g g+p^{\alpha} 中有一个是奇数,设这个奇数是 G ,则 \gcd(G,2p^{\alpha})=1

    由欧拉定理, \delta_{2p^{\alpha}}(G)\mid\varphi(2p^{\alpha})

    G^{\delta_{2p^{\alpha}}(G)}\equiv 1\pmod {2p^{\alpha}} ,故:

    G^{\delta_{2p^{\alpha}}(G)}\equiv 1 \pmod {p^{\alpha}}

    利用 G 为模 p^{\alpha} 的原根可知 \varphi(p^{\alpha})\mid\delta_{2p^{\alpha}}(G)

    结合 \varphi(p^{\alpha})=\varphi(2p^{\alpha}) 可知 G 为模 2p^{\alpha} 的原根。

    证毕

  • m\ne 2,4,p^{\alpha},p^{\alpha} ,其中 p 为奇素数, \alpha\in\mathbb{N}^*

    定理 4 :对于 m\ne 2,4 ,且不存在奇素数 p \alpha \in \mathbb{N}^{*} 使得 m=p^{\alpha},2p^{\alpha} ,模 m 的原根不存在。

    证明:对于 m=2^{\alpha} \alpha\in\mathbb{N}^{*},\alpha\geq 3 ,则对任意奇数 a=2k+1 均有:

    \begin{aligned}a^{2^{\alpha-2}}&=(2k+1)^{2^{\alpha-2}}\\&\equiv 1+C_{2^{\alpha-2}}^1(2k)+C_{2^{\alpha-2}}^{2}(2k)^{2}\\&\equiv1+2^{\alpha-1}k+2^{\alpha-1}(2^{\alpha-2}-1)k^2\\&\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k)\\&\equiv 1 \pmod {2^{\alpha}}\end{aligned}

    其中最后一步用到 k (2^{\alpha-2}-1)k 同奇偶,故其和为偶数。

    m 不是 2 的幂,且 m 为符合题目条件的数,则可设 m=rt ,这里 2<r<t \gcd(r,t)=1

    此时,若 \gcd(a,m)=1 ,由欧拉定理可知:

    a^{\varphi(r)}\equiv 1 \pmod r\;,\quad a^{\varphi(t)}\equiv1\pmod t

    注意到 n>2 时, \varphi(n) 为偶数,所以:

    a^{\frac{1}{2}\varphi(r)\varphi(t)}\equiv 1\pmod {rt}

    进而:

    \delta_m(a)\leq\dfrac{1}{2}\varphi(r)\varphi(t)=\dfrac{1}{2}\varphi(rt)=\dfrac{1}{2}\varphi(m)<\varphi(m)

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

    证毕


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

最小原根的数量级

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

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


评论