数论补全计划:原根
数论补全计划:原根
第一节 基本定义与内容
定义1.1 阶:设(a,m)=1,m>1,使得an≡1(modm)成立的最小的n成为阶。记作ordm(a)。
定义1.2 原根:m是正整数,a是整数,若a模m的阶是ϕ(m),那么a为模m的一个原根。
定理1.1 如果(a,m)=1,且m>0,那么正整数x是同余方程ax≡1(modm)的一个解,当且仅当ordm(a)|x
证明 如果ordm(a)|x,那么ak×ordm(a)≡(aordm(a))k≡1k≡1(modm),显然成立。
反过来,令x=p×ordm(a)+q,满足0≤q<ordm(a),那么ap×ordm(a)+q≡(aordm(a))p×aq≡1k×aq≡aq(modm)。因为ax≡1(modm),所以aq≡1(modm)。由于0≤q<ordm(a),那么根据阶的定义,q=0,所以ordm(a)|x
推论1.1 如果(a,n)=1,且n>0,那么ordn(a)|ϕ(n)。
证明 由欧拉定理,结合定理1.1即可推出。
定理1.2 如果(a,n)=1,且n>0,那么ai≡aj(modn)当且仅当i≡j(modordn(a))。
证明 请读者尝试自行证明。
证明可能所需要用到的引理 如果(c,m)=1且m>0,而且有ac≡bc(modm),那么有a≡b(modm)
上述引理为同余的消去律,是一个重要的定律。
定理1.3 如果(r,n)=1且n>0,如果r是模n的一个原根,那么r1,r2,...,rϕ(n)构成了一个模n的既约剩余系。
补充定义 既约剩余系:在每个剩余类选取1个与m互质的代表元构成的剩余系。
补充性质 容易看出,既约剩余系的判定依据是:所有数与n互质,且任意两个不同余。
证明 首先由于(r,n)=1,所以(rk,n)=1,所有数都与n互质;假设有两个同余,即ri≡rj(modn),i≠j,那么由定理1.2可知道,i≡j(modordn(a))。更进一步,i≡j(modϕ(n)),由于1≤i,j≤ϕ(n),所以i=j,矛盾,所以命题得证。
定理1.4 如果ordn(a)=t,那么有ordn(au)=t(t,u)
证明 令s=ordn(au),v=(t,u),t=t1v,u=u1v。那么(t1,u1)=1。
首先有,(au)t1=(au1v)t/v=(at)u1≡1(modn),(因为ordn(a)=t)。
那么我们根据定理1.1即可得出s|t1
另一方面,由于(au)s=aus≡1(modn),所以t|us,即t1v|u1vs,那么t1|u1s,由于(t1,u1)=1,所以t1|s。综合两方面,得出s=t1。原命题得证。
推论1.2 如果r是模n原根,且n>1,那么ru是模n的一个原根当且仅当(u,ϕ(n))=1。
证明 由定理1.4可知ordn(ru)=ordn(r)(u,ordn(r))=ϕ(n)(u,ϕ(n))。
当且仅当(u,ϕ(n))=1时,命题成立。
定理1.5 如果n有一个原根,那么它有ϕ(ϕ(n))个原根。
证明 令r为模n的一个原根,那么定理1.3证明了r1,r2,...,rϕ(n)构成了一个模n的既约剩余系。由推论1.2知道,ru是模n的一个原根当且仅当(u,ϕ(n))=1。所以只有ϕ(ϕ(n))个u,从而有ϕ(ϕ(n))个模n原根。
第二节 素数的原根
定理2.1 (拉格朗日定理) 假设f(n)=anxn+an−1xn−1+...+a1x+a0是一个次数为n,首项系数an不能被p整除的整系数多项式,且1≤n,那么f(x)至多有n个模p不同余的根。
证明
来源 《初等数论及其应用(第五版)》
定理2.2 假设p是素数且d|p−1,那么多项式xd−1恰有d个模p不同余的根。
证明
来源 《初等数论及其应用(第五版)》
推论2.1 假设p是素数,且d|p−1,那么比p小且模p的阶为d的正整数个数不超过ϕ(d)
证明 对于每一个p−1的因子d,令F(d)表示模p的阶为d的正整数个数。
若F(d)=0,显然有F(d)≤ϕ(d),否则,有一个整数a模p的阶为d。因为ordp(a)=d,所以整数a1,a2,...ad是模p不同余的。由于(ad)k≡(ak)d≡1(modp)对于所有k成立,所以这些幂都是xd−1模p的根。由定理2.2知,xd−1恰有d个模p不同余的根。因此每一个模p的根都只同余于a1,a2,...ad的一个。由定理1.4,次数为d的a的幂都形如ak且(k,d)=1。由于恰有ϕ(d)个k满足。所以如果有一个模p阶为d的元素,就一定有ϕ(d)个比p小的这样的整数。因此F(d)≤ϕ(d)。
定理2.3 假设p是素数,且d|p−1,那么模p的阶为d且不同余的整数个数为ϕ(d)
2022年8月10日 01:41
The new online web source portal2.bsnl.in provided by Bharat Sanchar Nigam Limited allows loyalty rewards for each online transaction towards landline, mobile, broadband, BSNL Landline Bill Payment fiber optic internet (FTTH) before or after the due date and even after disconnection. Check the new process in step by step to pay BSNL bill quickly in online without login using credit card or debit card or internet banking payment.The new online web source portal2.bsnl.in provided by Bharat Sanchar Nigam Limited allows loyalty rewards for each online transaction towards landline, mobile, broadband.
2022年9月17日 01:21
Urdu is one of the main languages in the state, and this is the first language for Urdu Medium students, there are fewer schools are working in all districts of the state, all the applicable students also can download AP SSC Urdu Model Paper 2023 Pdf in chapter wise for all lessons of the course, AP SSC Urdu Question Paper download, and practice the Ibtedai Question bank to get better rank in all exams conducted by BSEAP. Urdu is one of the main languages in the state, and this is the first language for Urdu Medium students, there are fewer schools are working in all districts of the state, all the applicable students also can download AP SSC Urdu Model Paper 2023 Pdf in chapter wise for all lessons of the course.