数论概论读书笔记 28.幂模p与原根

幂模p与原根

如果a$a$和p$p$互素，费马小定理告诉我们，ap−1≡1 (mod p)$a^{p-1}\equiv 1(modp)$

辣么这个指数p−1$p-1$是唯一的使得结果为1的嘛

我们选一些a$a$和p$p$看一下

对于a=3,p=7$a=3,p=7$ ：指数只有为6时才取到1。

模p余1的a的最小次幂：

从表中可以看出，似乎有这样的性质：

• 最小指数e$e$似乎整除p−1$p-1$
• 总有一些指数需要到指数p−1$p-1$

为了方便，我们定义a$a$模p$p$的阶指ep(a)=[使得ae≡1(mod p)的最小e]$e_p(a)=[使得a^e\equiv 1(modp)的最小e]$

a$a$和p$p$要是互素的。

规定ep(a)≥1$e_p(a)\ge 1$ 显然ep(a)≤p−1$e_p(a)\le p-1$

次数整除性质 设a是不被素数p$p$整除的整数，假设an≡1 (mod p)$a^n\equiv 1(modp)$，则次数ep(a)$e_p(a)$整除n$n$，特别地ep(a)$e_p(a)$总整除p−1$p-1$

证明： 次数ep(a)$e_p(a)$的定义告诉我们

假设an≡1( mod p)$a^n\equiv 1(modp)$

设G=gcd(ep(a),n)$G=gcd(e_p(a),n)$

并设(u,v)$(u,v)$是方程ep(a)u−nv=G$e_p(a)u-nv=G$的正整数解。（可知一定有解）

现在有两种不同的方法计算aep(a)u$a^{e_p(a)u}$

这表明aG≡1( mod p)$a^G\equiv 1(modp)$ ，所以必有ep(a)≤G$e_p(a)\le G$

另一方面G | ep(a)$G|e_p(a)$，所以G=ep(a) | n$G=e_p(a)|n$

证毕。

下一个任务是观察具有最大可能次数，即ep(a)=p−1$e_p(a)=p-1$的数a

如果a是这样的数，则幂

必须都是模p$p$不同的。[如果幂不是全不相同，则对某指数1≤i<j≤p−1$1\le i<j\le p-1$有ai≡aj (mod p)$a^i\equiv a^j(modp)$，由于a,p互质，则有1≡aj−i (mod p)$1\equiv a^{j-i}(modp)$，由于j−i<p−1$j-i<p-1$，则矛盾]。这p−1$p-1$个不同的数取遍了[1,p−1]$[1,p-1]$。

这样的数很重要，为了方便，我们称这样的数g$g$为模p$p$的原根，即ep(g)=p−1$e_p(g)=p-1$。

回顾前面的那张表，5的原根是2,3， 7的原根是3,5 ，11的原根是2,6,7,8

可见原根可以不止一个，辣到底有多少个？所有素数都有原根吗？

原根定理 每个素数p$p$都有原根。更精确地，有恰好φ(p−1)$\phi (p-1)$个模p$p$的原根。

神奇！尽管原根定理没有指出求p$p$的原根的具体方法，但一旦能求得一个原根，就可以容易得求出其他原根（后面介绍）。求原根的常用方法是从小到大枚举正整数a=2,3,5,6……。因为原根的分布比较广。（思考为什么没有4）。

为啥没4？因为4(p−1)2≡2p−1≡1 (mod p)$4^{\frac{(p-1)}{2}}\equiv 2^{p-1}\equiv 1(modp)$，即4一定不是原根。（可见2的高次幂都不是）

证明： 对1∼p−1$1\sim p-1$之间的每个数a$a$，ep(a) | (p−1)$e_p(a)|(p-1)$ ，所以，对整数p−1$p-1$的每个因子d$d$，我们可能会问，有多少个ep(a)$e_p(a)$等于d$d$，由于要用，我们记这个数为ψ(d),1≤a<p$\psi (d),1\le a<p$。

则ψ(p−1)$\psi (p-1)$为模p$p$的原根个数。

设n$n$是整除p−1$p-1$的任何数，比如说p−1=nk$p-1=nk$，则可将多项式Xp−1−1$X^{p-1}-1$分解成Xnk−1=(Xn)k−1=(Xn−1)((Xn)k−1+(Xn)k−2+...+(Xn)2+Xn+1)$X^{nk}-1=(X^n{)}^k-1=(X^n-1)((X^n{)}^{k-1}+(X^n{)}^{k-2}+...+(X^n{)}^2+X^n+1)$

我们数一下这些多项式模p$p$有多少个根。

首先,Xp−1−1≡0 (mod p)$X^{p-1}-1\equiv 0(modp)$恰好有p−1$p-1$个解，即[1,p−1]$[1,p-1]$这些。

另一方面，(Xn−1)≡0 (mod p)$(X^n-1)\equiv 0(modp)$至多有n$n$个解，且

至多有nk−n$nk-n$个解。

因此我们得到：

如果上式成立，则Xn−1$X^n-1$模p$p$恰有n$n$个根。这就证明了下述重要事实。

如果n | p−1$n|p-1$，则同余式Xn−1≡0 (mod p)$X^n-1\equiv 0(modp)$恰好有n$n$个根满足0≤X<p$0\le X<p$

现在再用另一种计数方法计数上面同余式的解的个数。

如果X=a$X=a$是一个解，则an≡1 (mod p)$a^n\equiv 1(modp)$，因此ep(a) | n$e_p(a)|n$，即ep(a)$e_p(a)$对应n$n$的一个因子d$d$

从这个角度，Xn−1≡0 (mod p)$X^n-1\equiv 0(modp)$解的个数等于

综合上面两个角度，我们得到一个结论：

若n$n$整除p−1$p-1$，则∑d|nψ(d)=n$\sum _{d|n}\psi (d)=n$

这个公式和欧拉函数的形式一样！

实际上这里ψ$\psi$就是φ$\phi$

首先，φ(1)=1$\phi (1)=1$，而ψ(1)=1$\psi (1)=1$

下面证明当n=q$n=q$为素数时，ψ(n)=φ(n)$\psi (n)=\phi (n)$

q的因数是1和q，所以ψ(q)+ψ(1)=q=φ(q)+φ(1)$\psi (q)+\psi (1)=q=\phi (q)+\phi (1)$

由于ψ(1)=φ(1)$\psi (1)=\phi (1)$，则ψ(q)=φ(q)$\psi (q)=\phi (q)$

n=q2$n=q^2$和n=q1q2$n=q_1{q}_2$也可以类似证明

通过从小的n$n$值到较大的n$n$的值的研究，说明了对每个n$n$证明φ(n)=ψ(n)$\phi (n)=\psi (n)$的思路。

更正式地，可以给出归纳证明，这里不展示了。

综上，我们已证明对整除p−1$p-1$的每个整数n$n$，恰好有φ(n)$\phi (n)$个数a$a$使得ep(a)=n$e_p(a)=n$，取n=p−1$n=p-1$，则φ(p−1)$\phi (p-1)$为原根个数。显然，每个素数至少有一个原根。

阿廷猜想 有无穷多个素数p$p$使得2是模p$p$的原根。

广义阿廷猜想 设整数a$a$不是完全平方也不等于−1$-1$，则有无穷多个素数p$p$使得a$a$是模p$p$的原根。

一个题目

答案是0

一个拓展