原根学习笔记

· · 个人记录

阶

定义

设 a,m\in \mathbb{N}^+，且 \gcd(a,m)=1，使得 a^x\equiv 1\pmod{m} 成立的最小正整数 x，称为 a 模 m 的阶，记为 \delta_m(a) 或 \operatorname{ord}_m(a)。

阶的性质

约定：以下默认 a,m\in \mathbb{N}^+，且 \gcd(a,m)=1，即 \operatorname{ord}_ma 存在。

性质 1

#### 证明 考虑反证，假设存在两个数 $i\ne j$，且 $a^i\equiv a_j\pmod{m}$，则有 $a^{\mid i-j\mid}\equiv 1\pmod{m}$。 又显然有 $0\lt \mid i-j\mid \lt \delta_m(a)$，与阶的最小性矛盾，故原命题成立。 ### 性质 2 若 $a^n\equiv 1\pmod{m}$，则 $\delta_m(a)\mid n$。 #### 证明 对 $n$ 除以 $\delta_m(a)$ 作带余除法，设 $n=\delta_m(a)\times q+r,0\le r\lt \delta_m(a)$。 若 $r\gt 0$，则 $$ a^r\equiv a^r\times a^{\delta_m(a)\times 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 设 $a,b,m\in \mathbb{N}^+$，且 $\gcd(a,m)=\gcd(b,m)=1$，则 $$ \delta_m(a\times b)=\delta_m(a)\times \delta_m(b) $$ 的充分必要条件是 $$ \gcd(\delta_m(a),\delta_m(b))=1 $$ #### 证明 - 必要性：由 $a^{\delta_m(a)}\equiv 1\pmod{m}$ 及 $a^{\delta_m(b)}\equiv 1\pmod{m}$，可知： $$ (a\times b)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1\pmod{m} $$ 由性质 2 可知，有： $$ \delta_m(a\times b)\mid \operatorname{lcm}(\delta_m(a),\delta_m(b)) $$ 又由于 $\delta_m(a\times b)=\delta_m(a)\times \delta_m(b)$，故有： $$ \delta_m(a)\times \delta_m(b)\mid \operatorname{lcm}(\delta_m(a),\delta_m(b)) $$ 即 $\operatorname{lcm}(\delta_m(a),\delta_m(b))=1$。 - 充分性：由 $(a\times b)^{\delta_m(a\times b)}\equiv 1\pmod{m} 1\equiv(a\times b)^{\delta_m(a\times b)}\equiv ((a\times b)^{\delta_m(a\times b)})^{\delta_m(b)}\equiv (a\times b)^{\delta_m(a\times b)\times \delta_m(b)}\pmod{m} (a\times b)^{\delta_m(a\times b)\times \delta_m(b)}\equiv a ^{\delta_m(a\times b)\times \delta_m(b)}\times b^{\delta_m(a\times b)\times \delta_m(b)}\equiv a^{\delta_m(a\times b)\times \delta_m(b)}\pmod{m}

故 \delta_m(a)\mid \delta_m(a\times b)\times \delta_m(b)，且 \gcd(\delta_m(a),\delta_m(b))=1，故有

\delta_m(a)\mid \delta_m(a\times b)

对称地，有

\delta_m(b)\mid \delta_m(a\times b)

所以

\delta_m(a)\times \delta_m(b)\mid \delta_m(a\times b)

另一方面，有

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

故

\delta_m(a\times b)\mid \delta_m(b)

综合以上两点即得

\delta_m(a\times b)=\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(\delta_m(a),k)}

证明

(a^k)^{\delta_m(a^k)}\equiv a^{k\ \times\ \delta_m(a^k) }\equiv1\pmod{m}

故有

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

另一方面，由 a^{\delta_m(a)}\equiv 1\pmod{m}，可得：

(a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}}\equiv (a^{k})^{\frac{\delta_m(a)}{\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}^+,g\in \mathbb{Z}，若 \gcd(g,m)=1，且 \delta_m(g)=\varphi(m)，则称 g 为 模 m 的原根。

即 g 满足 \delta_m(g)=\mid\mathbb{Z}^+_m\mid=\varphi(m)。当 m 是质数时，有 \forall i\in(0,m),h^i \bmod m 的结果互不相同。

原根判定定理

设 m\ge 3,\gcd(g,m)=1，则 g 是模 m 的原根的充要条件为，对于 \varphi(m) 的每个素因子 p，都有 g^{\frac{\varphi(m)}{p}}\not\equiv 1\pmod{m}。

原根个数

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

证明

若 m 有原根 g，则：

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

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

而满足 \gcd(\varphi(m),k)=1 且 1\le k \le \varphi(m) 的 k 有 \varphi(\varphi(m)) 个，所以原根就有 \varphi(\varphi(m)) 个。

原根存在定理

一个数 m 存在原根当且仅当 m=2,4,p^{\alpha},2\times p^{\alpha}，其中 p 为奇素数，\alpha \in \mathbb{N}^+。

证明

Part 1

当 m=2,4 时，原根显然存在。

Part 2

当 m=p^{\alpha}时，其中 p 为奇素数，\alpha \in \mathbb{N}^+。

定理 1

对于奇素数 p，p 有原根。

先证明一个引理，设 a 与 b 是与 p 互质的两个整数，则存在 c\in \mathbb{Z} 使得 \delta_p(c)=\operatorname{lcm}(\delta_p(a),\delta_p(b))。

先把 \delta_p(a),\delta_p(b) 表示成质因数分解的形式：

\delta_p(a)=\prod^{k}_{i=1}p_i^{\alpha_i},\delta_p(b)=\prod^{k}_{i=1}p_i^{\beta_i}

再将他们表示为如下形式：

\delta_p(a)=\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}\times \prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i} \delta_p(b)=\frac{\delta_p(b)}{\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}}\times \prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}

则由阶的性质 4，可得：

\begin{aligned} \delta_p(a^{\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}})&=&\dfrac{\delta_p(a)}{\gcd(\delta_p(a),\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}})} \\&=&\dfrac{\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}\times \prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}{\gcd(\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}\times \prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i},\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}})} \\&=&\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i} \end{aligned}

同理得：

\delta_p(b^{\frac{\delta_p(b)}{\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}}})=\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}

又因为显然有 \gcd(\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i},\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i})=1，\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}\times \prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}=\operatorname{lcm}(\delta_p(a),\delta_p(b))，则再由阶的性质 1，可得：

\begin{aligned} \delta_p(a^{\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}}\times b^{\frac{\delta_p(b)}{\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}}})&=&\delta_p(a^{\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}})\times \delta_p(b^{\frac{\delta_p(b)}{\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}}}) \\&=&\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}\times\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i} \\&=&\operatorname{lcm}(\delta_p(a),\delta_p(b)) \end{aligned}

于是令 c=a^{\frac{\delta_p(a)}{\prod^{k}_{i=1}p_i^{[\alpha_i\gt \beta_i]\alpha_i}}}\times b^{\frac{\delta_p(b)}{\prod^{k}_{i=1}p_i^{[\alpha_i\le \beta_i]\beta_i}}} 则命题得证。

回到原命题，对 i,j\in[1,p-1] 两两使用引理，可知存在 g\in \mathbb{Z} 使得

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

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

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

的根。

下证拉格朗日定理，即同余方程 f(x)\equiv 0\pmod p 最多有 \operatorname{deg} (f(x)) 个解，其中 \operatorname{deg} (f(x)) 为 f(x) 最高次项系数。

设 f(x)=\sum^{n}_{i=0} a_{i}x^{i}\ (p\nmid a_n )，其中 p 为质数。

设 f(x)\equiv 0\pmod p有 k 个不同的解 x_1,x_2,\cdots,x_k\ (k\le n)，\operatorname{deg} (g(x))=n-k 且 (x^{n-k})\times g(x)=a_n，则显然有：

f(x)\equiv g(x)\prod^{k}_{i=1}(x-x_i)\pmod p

回到原命题，设 f(x)\equiv 0\pmod p有 n+1 个不同的解 x_1,x_2,\cdots,x_n,x_{n+1}，则由上式，对于 x_1,x_2,\cdots,x_n 有：

f(x)\equiv a_n\prod^{k}_{i=1}(x-x_i)\pmod p

令 x=x_{x+1}，则

f(x_{n+1})\equiv a_n\prod^{k}_{i=1}(x_{n+1}-x_i)\equiv 0\pmod p

而中间显然不是 p 的倍数，因此假设矛盾。故原命题得证。

由拉格朗日定理，可知 x^{\delta_p(g)}\equiv 1\pmod{m} 方程的次数 \delta_p(g)\ge p-1。

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

综上可知 g 为模 m 的原根。故对于奇素数 p，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& \tbinom{p-1}{0} g^{p-1}+\tbinom{p-1}{1} p\times g^{p-2}\pmod {p^2} \\&\equiv&g^{p-1}+p(p-1) g^{p-2}\pmod {p^2} \\&\equiv&1-p\times g^{p-2}\pmod {p^2} \\&\not\equiv&1\pmod {p^2} \end{aligned}

接下来证明若 g 是一个满足引理条件的原根，则 \forall \alpha \in \mathbb{N}^+，g 是模 p^{\alpha} 的原根。

首先，证明下面的结论：\forall \beta \in \mathbb{N}^+，都可设

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

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

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

结合 p\nmid k_{\beta} 可知命题对 \beta +1 成立。所以命题对任意 \beta \in \mathbb{N}^+ 都成立。

其次，由欧拉定理，有 \delta_{p^{\alpha}}(g)\mid p^{\alpha-1}(p-1)。

而由 g 为模 p 的原根，及 g^{\delta_{p^{\alpha}}(g)}\equiv 1\pmod {p^{\alpha}}。

所以可设 \delta_{p^{\alpha}}(g)= p^{\beta-1}(p-1),\beta\in[1,\alpha]。

利用之前的结论，可知：

g^{\varphi(p^{\beta})}\not\equiv1 \pmod {p^{\beta+1}}

故

g^{\delta_{p^{\alpha}}(g)}\not\equiv1 \pmod {p^{\beta+1}}

结合 g^{\delta_{p^{\alpha}}(g)}\equiv1\pmod {p^{\alpha}} 可知 \beta\ge \alpha。

综上可知，\beta= \alpha，即：

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

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

Part 3

当 m=2p^{\alpha}时，其中 p 为奇素数，\alpha \in \mathbb{N}^+。

设 g 是模 p^{\alpha} 的原根，则 g+p^{\alpha} 也是模 p^{\alpha} 的原根。

在 g 和 g+p^{\alpha} 中有一个是奇数，设其为 G，则 \gcd(G,g+p^{\alpha})=1。

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

而 G^{\delta_{2p^{\alpha}}(G)}\equiv1 \pmod {2p^{\alpha}}，故：

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

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

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

Part 4

当 m\ne2,4,p^{\alpha},2\times p^{\alpha}，其中 p 为奇素数，\alpha \in \mathbb{N}^+。

对于 m=2^{\alpha}，\alpha \in \mathbb{N}^+，\alpha \ge3，则对于任意奇数 a=2k+1 均有：

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

有 k 和 (2^{\alpha-2}-1)k^2 奇偶性相同，故其和为偶数，故有：

(a^2)^{\alpha-2}\equiv 1 \pmod {2^{\alpha}}

其中 m 不是 2 的幂，且 m 为符合命题条件的数，则可设 m=rt，这里 2\lt r\lt t 且 \gcd(r,t)=1。

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

\begin{aligned} a^{\varphi(r)}\equiv 1 \pmod r \\a^{\varphi(t)}\equiv 1\pmod t \end{aligned}

注意到 n\gt 2 时，有 2\mid\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 个定理，我们便给出了一个数存在原根的充要条件。