原根
一些说明
- 令 \(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)\)
所以定理得证。