原根
一些说明
- 令 $p\in Prime$ 表示 $p$ 是一个素数。
一些定义
由欧拉定理可以知道，对于 $a\in Z,m\in Z^+,(a,m)=1$，则：
$$
a^{\phi(m)}\equiv 1\bmod m
$$
因此，对于假设（即在 $a$ 和 $m$ 互素的前提下），满足同余式 $a^n\equiv 1\bmod m$ 的最小正整数 $n$ 存在，这个数称为 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。若 $m\in Z^+,a\in Z,(a,m)=1,\delta_m(a)=\phi(m)$，则称 $a$ 为模 $m$ 的原根。
一些性质
- 若 $a^n\equiv 1\bmod m$，则 $\delta_m(a)|n$。
证明：设 $n=\delta_m(a)\times 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\bmod m
$$
与阶的定义矛盾。所以 $r=0$ 。证毕。
- 设 $m\in Z^+,a,b\in Z,\gcd(a,m)=\gcd(b,m)=1$，则 $\delta_m(ab)=\delta_m(a)\delta_m(b)$ 的充分必要条件是 $\gcd(\delta_m(a),\delta_m(b))=1$
必要性：$a^{\delta_m(a)}\equiv 1\bmod m,b^{\delta_m(b)}\equiv 1\bmod m \Rightarrow (ab)^{lcm(\delta_m(a),\delta_m(b))}\equiv 1\bmod m$。
性质 $1$ 可以得到：
$$
\delta_m(ab)|lcm(\delta_m(a),\delta_m(b))\Rightarrow \delta_m(a)\delta_m(b)|lcm(\delta_m(a),\delta_m(b))\Rightarrow \gcd(\delta_m(a),\delta_m(b))=1
$$充分性：
$$
(ab)^{\delta_m(ab)}\equiv 1\bmod m\Rightarrow 1\equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)}\bmod m\Rightarrow\delta_m(a)|\delta_m(ab)
$$
同理，我们可以得到：
$$
\delta_m(b)|\delta_m(ab)
$$
所以：
$$
\delta_m(a)\delta_m(b)|\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\bmod m\Rightarrow \delta_m(ab)|\delta_m(a)\delta_m(b)
$$
所以：
$$
\delta_m(ab)=\delta_m(a)\delta_m(b)
$$证毕。
- 设 $k\in N,m\in N^+,a\in Z,\gcd(a,m)=1$，则：
$$
\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}
$$
证明：
注意到：
$$
a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1\bmod m\Rightarrow \delta_m(a)|k\delta_m(a^k)\Rightarrow \dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}|\delta_m(a^k)
$$
另一方面，由 $a^{\delta_m(a)}\equiv 1\bmod 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\bmod m
$$
所以：
$$
\delta_m(a^k)|\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}
$$
所以有：
$$
\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}
$$证毕。
一些定理
（欧拉定理）$m\in Z^+,\forall a\in Z^+,(a,m)=1,s.t.a^{\phi(m)}\equiv1\bmod m$
（费马小定理）$p\in Prime\Rightarrow \forall a\in Z^+,(a,p)=1,s.t.a^{p-1}\equiv 1\bmod p$
（拉格朗日定理）设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式：
$$
f(x)=a_nx^n+a_{n-1}x^{n-1}+…+a_0(p\nmid a_n)
$$
的同余方程 $f(x)\equiv 0\bmod p$ 在模 $p$ 意义下至多有 $n$ 个不同解。
证明：
对 $n$ 使用数学归纳法。当 $n=0$ 时，因为 $p\nmid a_n$ 定理显然成立。
若定理对于 $\deg f<n$ 都成立，假设存在一个 $f,\deg f=n$，且 $f$ 至少有 $n+1$ 个不同的解：$x_0,x_1,x_2,…x_n$
设 $f(x)-f(x_0)=(x-x_0)g(x)$，则 $g(x)$ 在模 $p$ 意义下是一个至多 $n-1$ 次的多项式。注意到：
$$
\forall i,1\le i\le n,s.t.(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0 \bmod p
$$
而 $x_i\not\equiv x_0\bmod p$，所以 $g(x_i)\equiv 0\bmod p$，所以 $g(x)\equiv 0\bmod p$ 有至少 $n$ 个根，与假设矛盾。证毕。
- 设 $a$ 与 $b$ 是与 $p$ 互素的两个整数，则存在 $c\in Z$ 使得 $\delta_p(c)=lcm(\delta_p(a),\delta_p(b))$
- 证明：
- 设 $r=\delta_p(a),t=\delta_p(b),r=\prod\limits_{j=1}^{s}p_j^{\alpha_j},t=\prod\limits_{j=1}^{s}p_j^{\beta_j},\max(\alpha_j,\beta_j)>0$
注：这里可能会有读者疑惑于为什么 $r$ 和 $s$ 的质因数种类是一样的，实际上并不是这样，我们可以通过给另一个补 $0$ 来完成上面的式子的补全。
令 $l=\prod\limits_{j=1}^sp_j^{\alpha_j}\times[\alpha_j\le\beta_j],m=\prod\limits_{j=1}^sp_j^{\beta_j}\times[\alpha_j>\beta_j]$，记 $r=lx,t=my$，则我们有：$\gcd(x,y)=1,lcm(r,t)=xy$。
由性质 $3$ ，我们得到 $\delta_p(a^l)=x,\delta_p(b^m)=y$，则由性质 $2$，$\delta_p(a^lb^m)=xy=lcm(\delta_p(a),\delta_m(b))$，即取 $c=a^lb^m$ 即可。
存在模 $p$ 的原根 $g$ ，使得 $g^{p-1}\not\equiv 1\bmod p^2$
易知，$g+p$ 也是原根，设 $p$ 满足条件，否则那么定理成立。
我们有 $(g+p)^{p-1}\equiv C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2}\equiv1-pg^{p-2}\not\equiv 1\bmod p^2$
对于奇素数 $p$ ，$p$ 有原根。
证明：
对 $1$ 到 $(p-1)$ 依次两两使用定理 $4$ ，可以知道存在 $g\in Z$ 有：
$$
\delta_p(g)=lcm(\delta_p(1),\delta_p(2),…,\delta_p(p-1))
$$
这说明 $\delta_p(j)|\delta_p(g),j=1,2,…p-1$，所以 $j=1,2,…p-1$ 都是同余方程：
$$
x^{\delta_p(g)}\equiv 1\bmod p
$$
的解。由拉格朗日定理，可以知道 $\delta_p(g)\geq p-1$，由费马小定理，易知 $\delta_p(g)\le p-1$ 所以 $\delta_p(g)=p-1=\phi(p)$所以 $g$ 为 $p$ 的原根。
设 $g$ 满足定理 $5$ ，那么对任意的 $\beta\in \Bbb{N}^*$ 都可以设：$g^{\phi(p^{\beta})}\equiv 1+p^\beta\times k_{\beta}\bmod p^{\beta+1}$，其中 $p\not|k_\beta$
证明：$\beta=1$ 是平凡的。设上式对 $\beta$ 成立，则
$$
g^{\phi(p^{\beta+1})}=(g^{\phi(p^\beta)})^p=(1+p^\beta\times k_\beta)^p\equiv1+p^{\beta+1}\times k_\beta\bmod p^{\beta+2}
$$对于奇素数 $p,\alpha \in \Bbb{N}^*,p^{\alpha}$ 有原根。
证明：设 $g$ 是一个满足定理 $5$ 的一个模 $p$ 的原根，记 $\delta=\delta_{p^\alpha}(g)$ ，那么由欧拉定理有：
$$
\phi(p^\alpha)=p^{\alpha-1}(p-1)\
$$
由性质 $1$ 可以得到：
$$
\delta|p^{\alpha-1}(p-1)
$$
而 $g^\delta\equiv 1\bmod p^\alpha\Rightarrow g^\delta\equiv 1\bmod p$ ，所以 $g^\delta\equiv 1\bmod p,g^{p-1}\equiv 1\bmod p$ ，由性质 $1$ 可以得到 $(p-1)|\delta$ ，所以有 $\delta=p^{\beta-1}(p-1)=\phi(p^\beta),1\le \beta\le \alpha$。由定理 $7$ 我们知道：
$$
g^{\phi(p^\beta)}\not\equiv 1\bmod p^{\beta+1}\Rightarrow g^\beta\not\equiv 1\bmod p^{\beta+1}
$$
又因为 $p^\beta\equiv 1\bmod p^\alpha \Rightarrow \beta\ge \alpha$，所以 $\beta=\alpha$。所以 $g$ 是 $p^\alpha$ 的原根。对于奇素数 $p,\alpha \in \Bbb{N}^*,2p^{\alpha}$ 有原根。
证明：设 $g$ 是模 $p^\alpha$ 的原根，那么 $g+p^\alpha$ 也是模 $p^\alpha$ 的原根。设 $G$ 是这两者的奇数，则根据原根的定义，由 $\gcd(G,2p^\alpha)=1$ 。由欧拉定理和性质 $1$ ，设 $\delta=\delta_{2p^\alpha}(G)$，则有 $\delta|\phi(2p^\alpha)$。
而 $G^{\delta}\equiv 1\bmod 2p^\alpha$ ，故 $G^{\delta}\equiv 1\bmod p^\alpha$ 。利用 $G$ 为模 $p^\alpha$ 的原根可以知道 $\phi(p^\alpha)|\delta$，又因为 $\phi(p^\alpha)=\phi(2p^\alpha)$，所以可以知道 $G$ 为模 $2p^\alpha$ 的原根。
对于奇数 $a$ ，总存在 $m=2^\alpha,\alpha \ge 3,s.t.a^{2^{\alpha-2}}\equiv 1\bmod m$
设 $a=2k+1$，令 $\alpha =3$ 则：
$$
a^{2}=(2k+1)^2=4k^2+4k+1=4k(k+1)+1\bmod 8
$$
通过对 $k$ 的奇偶性讨论可以知道当 $\alpha=3$ 时定理成立。设定理对 $\alpha$ 成立，那么：
$$
a^{2^{\alpha-2}}=k2^\alpha+1\
a^{2^{\alpha-1}}=(k2^\alpha+1)^2=k^22^{2\alpha}+k2^{\alpha+1}+1\equiv 1\bmod 2^{\alpha+1}
$$
归纳可知，定理成立。对于所有 $m\not\in{1,2,4,p^\alpha,2p^\alpha},(\alpha\in\Bbb{N}^*)$，对于任意 $a\in \Bbb{Z},\gcd(a,m)=1$ ，都有 $\delta_m(a)<\phi(m)$ ，即模 $m$ 的原根不存在。
如果 $m$ 是 $2$ 的幂，根据定理 $10$ 可以知道原根不存在。
否则，令 $m=rt,(r,t)=1,2<r<t$ ，则 $\phi(m)=\phi(r)\phi(t)$ 因为当 $n>2$ 时 $\phi(n)$ 为偶数，所以有 $a^{\frac 12 \phi(r)\phi(t)}=(a^{\frac 14\phi(r)\phi(t)})^2,a^{\phi(r)\phi(t)}=(a^{\frac 12\phi(r)\phi(t)})^2\equiv 1\bmod m$
经过讨论后不难发现，$a^{\frac 12\phi(r)\phi(t)}\equiv 1\bmod m$
所以 $\delta_m(a)\le \frac 12\phi(m)$
所以定理得证。