Primitive Root
前置知识¶
这里只给出拉格朗日定理的证明。
拉格朗日定理:设
为素数,对于模 p 意义下的整系数多项式 p f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0(p\not\mid a_n) 的同余方程
在模 f(x)\equiv 0\pmod p 意义下至多有 p 个不同解。 n
证明:对
若命题对于
可设
而
所以,命题对
证毕
阶¶
阶:由欧拉定理可知,对
, a\in \mathbb{Z} ,若 m\in\mathbb{N}^{*} ,则 \gcd(a,m)=1 。 a^{\varphi(m)}\equiv 1\pmod m 因此满足同余式
的最小正整数 a^n \equiv 1 \pmod m 存在,这个 n 称作 n 模 a 的阶,记作 m 。 \delta_m(a)
性质¶
性质
: 1 模 a,a^2,\cdots,a^{\delta_m(a)} 两两不同余。 m
证明:考虑反证,假设存在两个数
但是显然的有:
证毕
性质
:若 2 ,则 a^n \equiv 1 \pmod m 。 \delta_m(a)\mid n
证明:对
若
这与
证毕
据此我还可以推出:
若
,则有 a^p\equiv a^q\pmod m 。 p\equiv q\pmod{\delta_m(a)}
还有两个与四则运算有关的重要性质。
性质
:设 3 , m\in\mathbb{N}^{*} , a,b\in\mathbb{Z} ,则 \gcd(a,m)=\gcd(b,m)=1 \delta_m(ab)=\delta_m(a)\delta_m(b) 的充分必要条件是
\gcd\big(\delta_m(a),\delta_m(b)\big)=1
证明:
必要性
由
由前面所述阶的性质,有
又由于
即
充分性
由
故
对称地,同理可得
所以
另一方面,有
故
综合以上两点即得
证毕
性质
:设 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\big(\delta_m(a),k\big)}
证明:注意到:
另一方面,由
故:
综合以上两点,得:
证毕
原根¶
原根:设
, m \in \mathbb{N}^{*} 。若 a\in \mathbb{Z} ,且 \gcd(a,m)=1 ,则称 \delta_m(a)=\varphi(m) 为模 a 的原根。 m
原根判定定理¶
原根判定定理:若一个数
是模 g 的原根,则有对于 m 任何大于 \varphi(m) 且不为自身的因数 1 ,都有 p 。 g^{\varphi(m)/p}\not\equiv 1\pmod m
证明: 假设存在一个
由 裴蜀定理 得,一定存在一组
又有
又
故假设不成立,原命题成立。
证毕
原根个数¶
若一个数
有原根,则它原根的个数为 m 。 \varphi(\varphi(m))
证明:若
所以若
而满足
证毕
原根存在定理¶
原根存在定理:一个数
存在原根当且仅当 m ,其中 m=2,4,p^{\alpha},2p^{\alpha} 为奇素数, p 。 \alpha\in \mathbb{N}^{*}
我们来证明它,分成
-
m=2,4 -
m=p^{\alpha} p \alpha\in \mathbb{N}^* 定理 1:对于奇素数
p p 证明:先证一个引理:
引理:设
a b p c\in\mathbb{Z} \delta_p(c)=\operatorname{lcm}\big(\delta_p(a),\delta_p(b)\big) 证明:我们先将
\delta_m(a),\delta_m(b) \left(\delta_m(a)=\prod_{i=1}^k{p_i^{\alpha_i}},\delta_m(b)=\prod_{i=1}^k{p_i^{\beta_i}} \right) 接着将它们表示成如下形式:
\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 \delta_m\left(a^X\right)=\dfrac{\delta_m(a)}{\gcd\big(\delta_m(a),X\big)}=\dfrac {XY}X=Y 同理:
\delta_m\left(b^Z\right)=W 又因为显然有
\gcd(Y,W)=1 YZ=\operatorname{lcm}\big(\delta_p(a),\delta_p(b)\big) 1 \delta_m\left(a^Xb^Z\right)=\delta_m\left(a^X\right)\delta_m\left(b^Z\right)=YZ=\operatorname{lcm}\big(\delta_p(a),\delta_p(b)\big) 于是令
c=a^Xb^Z 证毕
回到原命题,对
1 \sim (p-1) g\in \mathbb{Z} \delta_p(g)=\operatorname{lcm}\big(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\big) 这表明
\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 \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 C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2}\\&\equiv g^{p-1}+p(p-1)g^{p-2}\\&\equiv 1-pg^{p-2}\\&\not\equiv 1 \pmod {p^2}\end{aligned} 证毕
回到原题,我们证明若
g \alpha\in\mathbb{N}^{*} g p^{\alpha} 首先,证明下面的结论:对任意
\beta\in\mathbb{N}^{*} g^{\varphi(p^\beta)}=1+p^{\beta}\times k_{\beta} 这里
p\nmid k_{\beta} \beta=1 g \beta \begin{aligned}g^{\varphi(p^{\beta+1})}&=(g^{\varphi(p^{\beta})})^{p}\\&=(1+p^{\beta}\times k_{\beta})^p\\&\equiv 1+p^{\beta+1}\times 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