Primitive Root

前置知识

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

这里只给出拉格朗日定理的证明。

拉格朗日定理:设 p 为素数,对于模 p 意义下的整系数多项式

f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0(p\not\mid a_n)

的同余方程 f(x)\equiv 0\pmod p 在模 p 意义下至多有 n 个不同解。

证明:对 n 使用归纳法。当 n=0 时,由于 p\nmid a_0 ,故 f(x)\equiv 0\pmod p 无解,定理对 n=0 的多项式 f(x) 都成立。

若命题对于 \deg f<n f 都成立,由反证法,假设存在一个满足题目条件的 f 在模 p 意义下有着至少 n+1 个不同的解 x_0,x_1,\cdots,x_{n}

可设 f(x)-f(x_0)=(x-x_0)g(x) ,则 g(x) 在模 p 意义下是一个至多 n-1 次的多项式。现在由 x_0,x_1,\cdots,x_n 都是 f(x)\equiv 0\pmod p 的解,知对 1\leq i\leq n ,都有

(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0\pmod p

x_i \not\equiv x_0 \pmod p ,故 g(x_i)\equiv 0\pmod p ,从而 g(x)\equiv 0\pmod p 有至少 n 个根,与归纳假设矛盾。

所以,命题对 n 次多项式也成立,定理获证。

证毕


:由欧拉定理可知,对 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)

性质

性质 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 的原根。

原根判定定理

原根判定定理:若一个数 g 是模 m 的原根,则有对于 \varphi(m) 任何大于 1 且不为自身的因数 p ,都有 g^{\varphi(m)/p}\not\equiv 1\pmod m

证明: 假设存在一个 t<\varphi(p) 使得 a^t\equiv 1\pmod{p} \forall i\in\left[1,m\right]:a^{\frac{\varphi(p)}{d_{i}}}\not\equiv 1\pmod{p}

裴蜀定理 得,一定存在一组 k,x 满足 kt=x\varphi(p)+\gcd(t,\varphi(p)) ;由欧拉定理/费马小定理得 a^{\varphi(p)}\equiv 1\pmod{p} ;故有:

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

又有 t<\varphi(p) ,故 \gcd(t,\varphi(p))\leqslant t<\varphi(p)

\gcd(t,\varphi(p))\mid(\varphi(p)) ,故 \gcd(t,\varphi(p)) 必至少整除 {\frac{\varphi(p)}{d_{1}}},{\frac{\varphi(p)}{d_{2}}},\ldots,{\frac{\varphi(p)}{d_{m}}} 中的至少一个,设 \gcd(t,\varphi(p))\mid {\frac{\varphi(p)}{d_{i}}} ,则 a^{\frac{\varphi(p)}{d_{i}}}\equiv a^{\gcd(t,\varphi(p))}\equiv 1\pmod{p}

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

证毕

原根个数

若一个数 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 YZ=\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)=YZ=\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