原根存在性定理及其证明

· · 算法·理论

本文将要解决模 n 的原根何时存在的问题，这也就是 (\mathbb Z/n\mathbb Z)^{\times} 何时为循环群的问题，解决这个问题的核心思路考察特殊情况，然后运用中国剩余定理。

我们首先来看证明中需要用到的循环群的基本性质。

引理 1 \quad 设 G 为群，a,b\in G, \operatorname{ord}(a)=n,\operatorname{ord}(b)=m。若 ab=ba 且 \gcd(n,m)=1，则 \operatorname{ord}(ab)=nm。

证明 \quad 若 ab=ba，则 (ab)^k=a^kb^k。由 CRT，当 k 取遍 0 到 nm-1 时，a^kb^k 取遍 \{a^pb^q:(p,q)\in\mathbb N_{<n}\times\mathbb N_{<m}\}。但注意到若 a^pb^q=1，则 b^q=a^{-p}=a^{n-p}，故 b^{qn}=1，故 m\mid qn。由 \gcd(n,m)=1 可知 m\mid q，故一旦 q\neq 0 就有 m\leq q。同理，若 p\neq 0 则 n\leq p。因此，\{(ab)^k:0\leq k<nm\} 中只有 (ab)^0 取值为 1，其余元素皆不为 1，故 \operatorname{ord}(ab)\geq nm。最后，显然 (ab)^{nm}=1。这就证明了命题。\square

证明 (\mathbb Z/p\mathbb Z)^{\times} 循环

定理 1 \quad 设 F 是域，则任意有限子群 G\subset F^{\times} 皆为循环群。

证法 1 \quad 设 G 中阶最大的元素之阶为 m。由于 G 中所有元素的阶皆整除 m，可知 \forall x\in G, X^m=1。但 X^m-1=0 在 F 中至多有 m 个根，即 |G|\leq m，故如果 G 不是循环群则 m<|G| 导出矛盾。

证法 2 \quad 设 |G|=n，定义 \psi(d) 为 |G| 中阶为 d 的元素的个数。注意到 \psi(d)\neq 0 仅当 d\mid n。设 \varphi(d) 为欧拉函数，则

n=\sum_{d\mid n}\psi(d)=\sum_{d\mid n}\varphi(d).

如果 \psi(d)\neq 0，则存在 x\in G 使得 \operatorname{ord}(a)=d，是故 \langle x\rangle 是 X^d-1 的全部 d 个根。因此如果 y\in G 满足 \operatorname{ord}(y)=d，则 y\in\langle x\rangle。我们知道任何 m 阶循环群有 \varphi(m) 个生成元，故 \psi(d)\leq\varphi(d)。因此任何 d\mid n 都必须有 \varphi(d)=\psi(d)。从而 \psi(n)=\varphi(n)\geq 1，即 G 中存在 n 阶元，是故 G 是循环群。\square

推论 1 \quad 若 p 为素数，则 (\mathbb Z/p\mathbb Z)^{\times} 是循环群。

从中可以得出一些额外的有趣结果（但与本文目标关系不大），如：

推论 2 \quad 若 p 为素数，则 X^2+1=0 在 \mathbb Z/p\mathbb Z 中有解当且仅当存在一个 n 使得 p=4n+1。

证明 \quad 若 p=4n+1，则存在一个元素 x 使得 \{1,x,\cdots,x^{4n-1}\} 两两不同，而 (x^{2n})^2=x^{4n}=1，是故 x^{2n}=-1。于是 (x^n)^2=x^{2n}，故 x^n 是一个解。反之，若 x^2+1=0\pmod{p}，则 x^4=1，于是 4\mid p-1，故 p=4n+1。\square

证明 (\mathbb Z/p^m\mathbb Z)^{\times}\;(p\geq 3) 循环

引理 2 \quad \varphi(p^m)=p^m-p^{m-1}。

这是一个十分初等的结论，但它表明 |(\mathbb Z/p^m\mathbb Z)^{\times}|=p^m-p^{m-1}。接下来我们着手证明 (\mathbb Z/p^m\mathbb Z)^{\times} 是循环的。

引理 3 \quad 设 p 为素数，整数 k\geq 1，则

v_p\left(\binom{p^k}{i}\right)=k-v_p(i).

证明 \quad 我们有

\begin{aligned} v_p\left(\binom{p^k}{i}\right)&=v_p\big((p^k)!\big)-v_p(i!)-v_p\big((p^k-i)!\big)\\ &=\sum_{j=1}^{\infty}\left(\left\lfloor\frac{p^k}{p^j}\right\rfloor-\left\lfloor\frac{i}{p^j}\right\rfloor-\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\\ &=\sum_{j=1}^{k}\left(\left\lfloor\frac{p^k}{p^j}\right\rfloor-\left\lfloor\frac{i}{p^j}\right\rfloor-\left\lfloor\frac{p^k-i}{p^j}\right\rfloor\right)\\ &=\sum_{j=1}^{k}\left(p^{k-j}-\left\lfloor\frac{i}{p^j}\right\rfloor-\left\lfloor p^{k-j}-\frac{i}{p^j}\right\rfloor\right)\\ &=\sum_{j=1}^k\left(-\lfloor i/p^j\rfloor+\lceil i/p^j\rceil\right). \end{aligned}

若 p^j\mid i，则 -\lfloor i/p^j\rfloor+\lceil i/p^j\rceil=0，否则 -\lfloor i/p^j\rfloor+\lceil i/p^j\rceil=1。因此

\sum_{j=1}^k\left(-\lfloor i/p^j\rfloor+\lceil i/p^j\rceil\right)=k-v_p(i).

这就证明了引理。\square

推论 3 \quad 设 p 是奇素数，则

(p+1)^{p^k}\equiv 1+p^{k+1}\mod p^{k+2},\quad\forall k\in\mathbb Z_{\geq 0}.

证明 \quad 我们有

\begin{aligned} (p+1)^{p^k}&=1+p^{k+1}+\sum_{i=2}^{p^k}\binom{p^k}{i}p^i=1+p^{k+1}+\sum_{i=2}^{p^k}s_ip^{k-v_p(i)+i},&s_i\in\mathbb N. \end{aligned}

对于 i\geq 3，显然 i-v_p(i)\geq 2。对于 i=2，由于 p 是奇素数，故

\binom{p^k}{2}p^2=\frac{p^k(p^k-1)}{2}p^2=p^{k+2}s,\qquad\exists s\in\mathbb N,

从而 (p+1)^{p^k}\equiv 1+p^{k+1}\pmod{p^{k+2}}。\square

引理 4 \quad p+1 在 (\mathbb Z/p^m\mathbb Z)^{\times} 中是 p^{m-1} 阶元。

证明 \quad 由推论 3 得 (p+1)^{p^{m-1}}=1+p^m=1，故存在 k\leq m-1 使得 \operatorname{ord}(p+1)=p^k\mid p^{m-1}。但在 (\mathbb Z/p^m\mathbb Z)^{\times} 中必须有 (p+1)^{p^k}=1，而 (p+1)^{p^k}\equiv 1+p^{k+1}\pmod{p^{k+2}}，于是必有 p^{k+1}=0\pmod{p^m}，故 m\leq k+1，即 m-1\leq k。于是 k=m-1，即 \operatorname{p+1}=p^{m-1}。\square

引理 5 \quad 设 a 是 (\mathbb Z/p\mathbb Z)^{\times} 的任一生成元，则 a 在 (\mathbb Z/p^m\mathbb Z)^{\times} 中的阶为 (p-1)s，其中 s\in\mathbb Z_{>0}。

证明 \quad a^{\operatorname{ord}(a)}\equiv 1\pmod{p^m} 则自然 a^{\operatorname{ord}(a)}\equiv 1\pmod{p}，故 p-1|\operatorname{ord}(a)，得证。\square

定理 2 \quad (\mathbb Z/p^m\mathbb Z)^{\times} 是循环群。

证明 \quad 考虑引理 5 中的 a，有 (a^s)^{p-1}=1。则 \operatorname{ord}(a^s)=j。如果 j<p-1，则 a^{js}=1，即 \operatorname{ord}(a)\leq js<(p-1)s，矛盾，故 \operatorname{ord}(a^s)=p-1。由引理 4 知 \operatorname{ord}(p+1)=p^{m-1}。注意到 \gcd(p-1,p^{m-1})=1，于是由引理 1 和引理 2 知 \operatorname{ord}((p+1)a^s)=p^m-p^{m-1}=\varphi(p^m)，是故 (\mathbb Z/p^m\mathbb Z)^{\times}=\langle(p+1)a^s\rangle。\square

运用 CRT 分解

对于任意的 n=p_1^{k_1}\cdots p_r^{k_r}\in\mathbb Z_{\geq 2}，由中国剩余定理知

(\mathbb Z/n\mathbb Z)^{\times}\;\xrightarrow{\sim}\;\big(\mathbb Z/p_1^{k_1}\mathbb Z\big)^{\times}\times\cdots\times\big(\mathbb Z/p_r^{k_r}\mathbb Z\big)^{\times},

首先注意到如果 G_1,G_2 中有一个不循环，则 G_1\times G_2 肯定不循环。因此现在就来考察两个循环群的直积循环的条件。

引理 6 \quad 设 G_1,G_2 是有限的循环群，则 G:=G_1\times G_2 循环当且仅当 \gcd(|G_1|,|G_2|)=1。

证明 \quad 取 G_1,G_2 的生成元 x_1,x_2。如果 \gcd(|G_1|,|G_2|)=1，则 \operatorname{ord}((x_1,1))=|G_1|,\operatorname{ord}((1,x_2))=|G_2|，于是由引理 1 得 \operatorname{ord}((x_1,x_2))=|G_1|\left|G_2\right|=|G_1\times G_2| 故 G 循环。反之，如果 \gcd(|G_1|,|G_2|)=d>1，则对任意 (x_1,x_2)\in G 有

(x_1,x_2)^{\frac{|G_1|\left|G_2\right|}{d}}=\left(\big(x_1^{|G_2|/d}\big)^{|G_1|},\big(x_2^{|G_1|/d}\big)^{|G_2|}\right)=1,

故 \forall x=(x_1,x_2)\leq|G_1|\left|G_2\right|/d<|G|，故 G 不循环。\square

由此可以立即得出，如果 n 的分解中存在超过两个奇素数 p_1,p_2，则无论如何 \gcd\big(p_1^{k_1}(p_1-1),p_2^{k_2}(p_2-1)\big)\geq 2>1，故 (\mathbb Z/n\mathbb Z)^{\times} 要想循环充其量只能是 n=2^kp^m\,(p\geq 3) 或 n=2^k 的形式。对于前者，由引理 6 已经可知如果 k=1 则 (\mathbb Z/n\mathbb Z)^{\times}=(\mathbb Z/2p^m\mathbb Z)^{\times} 循环，如果 k\geq 2 则不循环。其次，我们已经知道 (\mathbb Z/2\mathbb Z)^{\times} 和 (\mathbb Z/4\mathbb Z)^{\times} 是循环的。因此现在留下的问题就是 (\mathbb Z/2^k\mathbb Z)^{\times} 对于 k\geq 3 是否是循环的。

证明 (\mathbb Z/2^k\mathbb Z)^{\times}\;(k\geq 3) 不循环

引理 8 \quad (1+2^2)^{2^k}\equiv 1+2^{k+2}\pmod{2^{k+3}}。

证明 \quad 由引理 3 展开计算知

(1+2^2)^{2^k}=\sum_{j=0}^{2^k}\binom{2^k}{j}2^{2j}=1+2^{k+2}+\sum_{j=2}^{2^k}\binom{2^k}{j}2^{2j}\equiv 1+2^{k+2}\mod 2^{k+3}. \square

引理 9 \quad 对于 k\geq 3，5 在 (\mathbb Z/2^k\mathbb Z)^{\times} 中的阶是 2^{k-2}。

证明 \quad 由引理 8 知 5^{2^{k-2}}\equiv 1+2^k=1\pmod{2^k}。反之，如果 j<k-2，则 5^{2^j}\equiv 1+2^{j+2}\neq 1\pmod{2^k}。因此 \operatorname{ord}(5)=2^{k-2}。\square

定理 3 \quad 对于 k\geq 3，有

(\mathbb Z/2^k\mathbb Z)^{\times}\xrightarrow{\sim}(\mathbb Z/2\mathbb Z)\times(\mathbb Z/2^{k-2}\mathbb Z),

其中同构的右端是加法群。

证明 \quad 首先 |(\mathbb Z/2^k\mathbb Z)^{\times}=2^{k-1}=|(\mathbb Z/2\mathbb Z)\times(\mathbb Z/2^{k-2}\mathbb Z)|。定义

\begin{aligned} (\mathbb Z/2\mathbb Z)\times(\mathbb Z/2^{k-2}\mathbb Z)&\longrightarrow(\mathbb Z/2^k\mathbb Z)^{\times}\\ (a,b)&\longmapsto(-1)^a5^b. \end{aligned}

我将证明 \varphi 是单射。考虑 \ker(\varphi)。如果 (-1)^a5^b=1 且 a\neq 0 即 a=1，则 5^b=-1，故 5^{2b}=1，故 2^{k-2}\mid 2b，由于 b\in\mathbb Z/2^{k-2}\mathbb Z，只能有 b=2^{k-3}，则 5^{2^{k-3}}\equiv 1+2^{k-1}\neq -1\pmod{2^k}，矛盾，于是只能有 a=0。若 a=0，则 5^b=12，故 2^{k-2}\mid b，故 b=0。从而 \ker(\varphi)=0，这就证明了 \varphi 是单射。由证明开头对元素个数的讨论可知 \varphi 确实是群同构。\square

推论 4 \quad 若 k\geq 3，则 (\mathbb Z/2^k\mathbb Z)^{\times} 不是循环群。

原根存在性定理

现在，综合以上所有情况，我们可以完成对原根存在性的讨论：

定理 4 \quad (\mathbb Z/n\mathbb Z)^{\times} 中存在原根当且仅当 n=2,4,p^m,2p^m，其中 p\geq 3 是奇素数。