首页 理论教育 初等数论基础:原根与n次剩余

初等数论基础:原根与n次剩余

时间:2023-10-19 理论教育 版权反馈
【摘要】:本节利用原根的理论来研究n次二项同余方程xn≡a,(a,m)=1.为此,需要引入指标的概念.设m∈Z,m>1且g是模m的原根.据命题7.3.1知1,g,g2,…,gφ-1是模m的简化剩余系.据本定理的及命题7.4.1,gi是n次剩余当且仅当|indggi=i.故1,g,g2,…,gφ-1中的n次剩余的个数就是0,1,2,…

初等数论基础:原根与n次剩余

本节利用原根的理论来研究n次二项同余方程xn≡a(modm),(a,m)=1.为此,需要引入指标的概念.设m∈Z,m>1且g是模m的原根.据命题7.3.1知1,g,g2,…,gφ(m)-1是模m的简化剩余系.于是,对任意a∈Z,只要(a,m)=1,就存在唯一的整数t∈{0,1,2,…,φ(m)-1}使得a≡gt(modm).此时,称t为a关于模m的以g为底的指标,记之为indga.即t=indga.

命题7.4.1 设g,g1是模m的原根,a,b∈Z且(a,m)=(b,m)=1.则

(1)indg1=0,indgg=1.

(2)indg(ab)≡(indga+indgb)(modφ(m)).

(3)indgan≡n·indga(modφ(m)),n是任意非负整数.

(4)indga≡(indg1a·indgg1)(modφ(m)).

(5)a≡b(modm)当且仅当indga≡indgb(modφ(m))当且仅当indga=indgb.

(6)若0≤t≤φ(m)-1,则indggt=t.

证明 利用定理7.1.3直接验证即可,留作习题.证毕.

下面用指标研究同余方程

xn≡a(modm),(a,m)=1.

设m≥2,n≥2.若同余方程xn≡a(modm),(a,m)=1有解,则称a为模m的n次剩余.否则称其为模m的n次非剩余.在模m原根存在的前提下,下面的结论从理论上解决了整数a是否为模m的n次剩余的问题.

定理7.4.2 设g是模m的原根,(a,m)=1,n≥2.

(1)a是模m的n次剩余当且仅当(n,φ(m))|indga.此时,同余方程xn≡a(modm)对模m有(n,φ(m))个解.

(2)模m的一个简化剩余系中恰有个模m的n次剩余.

证明 先证xn≡a(modm)有解当且仅当nx≡indga(modφ(m))有解.事实上,若有x0∈Z使得≡a(modm),则据命题7.4.1(3),(5)知n·indgx0≡indga(modφ(m)).这表明nx≡indga(modφ(m))有解.反之,若有x0∈Z使得(www.xing528.com)

nx0≡indga(modφ(m)),

则可设0≤x0≤φ(m)-1.于是由命题7.4.1(3),(6)知

利用命题7.4.1(5)知这表明xn≡a(modm)有解.

(1)据定理3.1.2及上述所证结论可知a是模m的n次剩余当且仅当(n,φ(m))|indga.此时,nx≡indga(modφ(m))关于模φ(m)有(n,φ(m))个解.设这些解为

x≡xi(modφ(m)),0≤xi≤φ(m)-1,i=1,2,…,(n,φ(m)).

据上一段的论证,是xn≡a(modm)的解,i=1,2,…,(n,φ(m)).由命题7.4.1(6)知

再据命题7.4.1(5)知这表明诸是xn≡a(modm)的两两不同的解.另外,若x≡y0(modm)是xn≡a(modm)的解,则据上段的讨论知x≡indgy0(modφ(m))是nx≡indga(modφ(m))的解.由0≤indgy0≤φ(m)-1知indgy0等于某个xi,即xi=indgy0,从而.故诸就是xn≡a(modm)关于模m的全部(n,φ(m))个解.

(2)由g是原根知1,g,g2,…,gφ(m)-1是模m的简化剩余系.据本定理的(1)及命题7.4.1(6),gi(0≤i≤φ(m)-1)是n次剩余当且仅当(n,φ(m))|indggi=i.故1,g,g2,…,gφ(m)-1中的n次剩余的个数就是0,1,2,…,φ(m)-1中能被(n,φ(m))整除的数的个数,这个数是 证毕.

例7.4.3 解同余方程x8≡3(mod11).

解 容易验证2是模11的一个原根且

20≡1(mod11),21≡2(mod11),22≡4(mod11),

23≡8(mod11),24≡5(mod11),25≡10(mod11),

26≡9(mod11),27≡7(mod11),28≡3(mod11),29≡6(mod11).

由于,据定理7.4.2知该方程有两个解.先解不定方程8x≡ind23(modφ(11)).这个方程实际上就是8x≡8(mod10).易知其解为x≡1,6(mod10).故原方程的解为x≡21,26(mod11),即x≡2,9(mod11).解毕.

注7.4.4 如前所述,本节只是在模m原根存在的前提下,从理论上解决了整数a是否为模m的n次剩余的问题.对模m原根不存在的情况,讨论起来相对复杂,我们在此就不涉及了,有兴趣的读者可查阅参考文献[10].

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈