一、原根

性质

性质1

$a,a^2,...,a^{\delta_m (a)}$模$m$两两不同。

证明

反证，设存在$0< i < j \leqslant \delta_m (a)$，且$a^i \equiv a^j\pmod{m}$。两边同除得$a^{\mid j-i\mid} \equiv1\pmod{m}$。$0 < j-i< \delta_m (a)$，则$\delta_m (a)$不为最小阶，矛盾。

性质2

若$a^n \equiv 1 \pmod{m}$，则$\delta_m (a) \mid n$。

证明

反证，设$n=\delta_m (a)q+r，0< r< \delta_m (a)$。 $$a^r \equiv a^r (a^{\delta_m (a)})^q \equiv a^n \equiv 1 \pmod{m}$$

$0 < r < \delta_m (a)$，则$\delta_m (a)$不为最小阶，矛盾。

另，若$a^p \equiv a^q \pmod{m}$，则$p \equiv q \pmod{\delta_m (a)}$。

性质3

$(a,m)=(b,m)=1$，则

\[\delta_m (ab)=\delta_m (a)\delta_m (b) \iff (\delta_m (a),\delta_m (b))=1 \]

证明

$A\Rightarrow B$：

由$a^{\delta_m (a)} \equiv 1\pmod{m}，b^{\delta_m (b) }\equiv 1\pmod{m}$，得

\[(ab)^{\left[ \delta_m (a),\delta_m (b)\right]} \equiv1 \pmod{m} \]

由性质2，

\[\delta_m (ab) \mid \left[ \delta_m (a),\delta_m (b)\right] \]

由$A$得

\[\delta_m (a) \delta_m (b) \mid \left[ \delta_m (a),\delta_m (b)\right] \]

即$B$

$B\Rightarrow A$：

由$ab^{\delta_m (ab)} \equiv 1\pmod{m}$，得

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

得$\delta_m (a) \mid \delta_m (ab)\delta_m (b)$。结合$B$得

\[\delta_m (a) \mid \delta_m (ab) \]

同理得

\[\delta_m (b) \mid \delta_m (ab) \]

再结合$B$得

\[\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)} (b^{\delta_m (b)})^{\delta_m (a)} \equiv 1 \pmod{m} \]

得

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

综上得$A$

性质4

设$k \in \mathbb{N},m \in \mathbb{N^*},a \in \mathbb{Z},(a,m)=1$，则

\[\delta_m (a^k)= \frac{\delta_m (a)}{(\delta_m (a),k)} \]

证明

\[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 \frac{\delta_m(a)}{(\delta_m(a),k)} \mid \delta_m (a^K) \]

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

\[\Rightarrow \delta_m(a^k) \mid \frac{\delta_m(a)}{(\delta_m(a),k)} \]

综上得

\[\delta_m(a^k) = \frac{\delta_m(a)}{(\delta_m(a),k)} \]

定义

设 $m \in \mathbf{N}^{*}$ ， $g\in \mathbf{Z}$ . 若 $(g,m)=1$ ，且 $\delta_m(g)=\varphi(m)$ ，则称 $g$ 为模 $m$ 的原根。

即 $g$ 满足$\delta_m(g) = \left| \mathbf{Z}_m^* \right| = \varphi(m)$ . 当 $m$ 是质数时，我们有 $g^i \bmod m,\,0 \lt i \lt m$ 的结果互不相同。

判定定理

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

证明

$A\Rightarrow B$：

反证，若有$g^{\frac{\varphi(m)}{p}}\equiv 1\pmod m$ ，$\frac{\varphi(m)}{p} < \varphi(m) = \delta_m(g)$，不满足阶的最小性，故原命题成立

$B\Rightarrow A$：

当$B$成立时，设存在 $g$不是模 $m$ 的原根。
则存在$t<\varphi(m)$ 使得 $g^t\equiv 1\pmod{m}$ .

由裴蜀定理(设 $a,b$ 是不全为零的整数，存在整数 $x,y$ , 使得 $ax+by=\gcd(a,b)$ ) 得，一定存在一组 $x,y$ 满足 $xt=y\varphi(m)+(t,\varphi(m))$ .

又由欧拉定理得 $g^{\varphi(m)}\equiv 1\pmod{m}$ ，故有：

\[1\equiv g^{xt}\equiv g^{y\varphi(m)+(t,\varphi(m))}\equiv g^{(t,\varphi(m))}\pmod{m} \]

由于 $(t, \varphi(m)) \mid \varphi(m)$ 且 $(t, \varphi(m))\leqslant t < \varphi(m)$ .

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

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

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

个数

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

证明

若 $m$ 有原根 $g$ ，则由阶的性质4得

\[\delta_m(g^k)=\dfrac{\delta_m(g)}{\left(\delta_m(g),k\right)}=\dfrac{\varphi(m)}{\left(\varphi(m),k\right)} \]

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

而满足 $\left(\varphi(m),k\right)=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 \mathbf{N}^{*}$

定理1

奇素数$p$有原根

证明

先证一个引理：

设 $a$ 与 $b$ 是与 $p$ 互素的两个整数，则存在 $c\in\mathbf{Z}$ 使得 $\delta_p(c)=\left[\delta_p(a),\delta_p(b)\right]$ .

证明

质因数分解 $$\delta_m(a)=\prod_{i=1}^k{p_i^{\alpha_i}},\delta_m(b)=\prod_{i=1}^k{p_i^{\beta_i}} $$

化成

\[\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，可得：

\[\begin{aligned} \delta_m\left(a^X\right)&=\dfrac{\delta_m(a)}{\left(\delta_m(a),X\right)}\\ &=\dfrac{XY}{X}\\ &=Y \end{aligned} \]

同理：
$ \delta_m\left(b^Z\right)=W $

又因为显然有 $(Y,W)=1$ ， $YW=\left[\delta_p(a),\delta_p(b)\right]$，则再由阶的性质 1，可得：

\[\begin{aligned} \delta_m\left(a^Xb^Z\right)&=\delta_m\left(a^X\right)\delta_m\left(b^Z\right)\\ &=YW\\ &=\left[\delta_p(a),\delta_p(b)\right] \end{aligned} \]

于是令 $c=a^Xb^Z$ 引例得证。

回到原命题，对 $1 \sim (p-1)$ 依次两两使用引理，可知存在 $g\in \mathbf{Z}$ 使得
$ \delta_p(g)=\left$\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\right]$

这表明 $\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 \mathbf{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 \binom{p-1}{0}g^{{p-1}+\binom{p-1}{1}pg} \pmod {p^2}\ &\equiv g^{{p-1}+p(p-1)g} \pmod {p^2}\ &\equiv 1-pg^{p-2} \pmod {p^2}\ &\not\equiv 1 \pmod {p^2} \end{aligned} $

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

首先，证明下面的结论：对任意 $\beta\in\mathbf{N}^{*}$ ，都可设
$ g^{\varphi(p\beta)}=1+p^{\beta} k_{\beta} $

这里 $p\nmid k_{\beta}$ 。事实上， $\beta=1$ 时，由 $g$ 的选取可知结论成立。现设上式对 $\beta$ 时成立，则
$ \begin{aligned} g^{\varphi(p)}&=\left(g^{{\varphi\left(p}\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\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)}\not\equiv 1\pmod {p^{\beta+1}}\implies 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}(p-1)=\varphi(p^\alpha) $

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

定理3

对于奇素数 $p$ ， $\alpha\in\mathbf{N}^{*}$ ， $2p^{\alpha}$ 的原根存在。

证明

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

在 $g$ 和 $g+p^{\alpha}$ 中有一个是奇数，设这个奇数是 $G$ ，则 $(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}$ 的原根。

定理4

对于 $m\ne 2,4$ ，且不存在奇素数 $p$ 及 $\alpha \in \mathbf{N}^{*}$ 使得 $m=p^{\alpha},2p^{\alpha}$ ，模 $m$ 的原根不存在。

证明

对于 $m=2^{\alpha}$ ， $\alpha\in\mathbf{N}^{*},\alpha\geq 3$ ，则对任意奇数 $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}}\\ &\equiv 1 \pmod {2^{\alpha}} \end{aligned} \]

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

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

此时，若 $(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$ 的原根不存在。