初等数论-第七章--原-根

154第七章原根原根是数论的理论和应用中一个很重要的概念。本章要介绍原根以及与它有关的基本知识。第一节指数及其基本性质定义1设m1，(a,m)=1，则使ar1(modm)(1)成立的最小的正整数r，称为a对模m的指数，记为m(a)，在不致误会的情况下，简记为(a)。由Euler定理，当r=(m)时式(1)成立，因此，恒有m(a)(m)。若ab(modm)，(a,m)=1，则显然有m(a)=m(b)。定义2若m(a)=(m)，则称a是模m的原根。例如，当m=7时，因为212，224，231(mod7)，所以7(2)=3。又因为313，322，336，344，355，361(mod7)，所以7(3)=6=(7)，3是模7的原根。以后，在谈到a对模m的指数时，总假定m1，(a,m)=1。定理1记=m(a)，则a0,a1,,a1对模m两两不同余。证明用反证法。若有0ij1，使得aiaj(modm)，则由(a,m)=1得到aji1(modm)，这与=m(a)的定义矛盾，所以定理成立。证毕。155定理1说明，若g是模m的原根，则g0,g1,,g(m)1构成模m的简化剩余系。定理2设=m(a)，r与r是正整数，则arar(modm)(2)的充要条件是rr(mod)。(3)特别地，ar1(modm)的充要条件是r。证明不妨设rr。因为(a,m)=1，所以式(2)等价于arr1(modm)。(4)若式(4)成立，记rr=qt，qN，0t，则由定义1，有ataqt=arr1(modm)。由m(a)的定义可知t=0，即rr，也即式(3)成立。必要性得证。若式(3)成立，则存在qN，使得rr=q，则由定义1，有arr=aq1(modm)，即式(4)成立，从而式(2)成立，充分性得证。取r=0，得到定理的第二个结论。证毕。推论m(a)(m)。证明由Euler定理及定理2得证。定理3设k是非负整数，则)),(()()(kaaammkm。证明记=m(a)，=m(ak)，=),(k，则由定理2及ak1(modm)可知。(5)由定理2及ak=(ak)1(modm)可知k，因此=),(),(|kkk。(6)由于1),(,),()(kkk，所以由式(6)可以推出。由此及式(5)得156到=。证毕。推论若m(a)=kl，k0，l0，则m(ak)=l。定理4等式m(ab)=m(a)m(b)(7)与(m(a),m(b))=1(8)是等价的。证明记1=m(a)，2=m(b)，3=m(ab)，=[1,2]。若式(7)成立，则12=3。由的定义和定理2，以及(ab)=ab1(modm)又得到3。因此3=，即12=[1,2]，所以(1,2)=1，即式(8)成立。若式(8)成立，则由定理2及1232323)(])[(aabab(modm)得到123。由式(8)推出13。同理可推出23。所以=[1,2]3。但是，由式(8)可知[1,2]=12，所以123。另一方面，由定理2及21)(ab1(modm)得到312。所以3=12，即式(7)成立。证毕。例1求1，2，3，4，5，6对模7的指数。根据定义1直接计算，得到7(1)=1，7(2)=3，7(3)=6，7(4)=3，7(5)=6，7(6)=2。例1中的结果可列表如下：a1234567(a)136362这样的表称为指数表。这个表就是模7的指数表。下面是模10的指数表：157a137910(a)1442例2若(a,m)=1，aa1(modm)，则m(a)=m(a)。解显然(a,m)=1。要证明的结论由ad1(modm)(a)d1(modm)即可得出。例3若nm，则n(a)m(a)。解由nm及定理2有)(ama1(modm))(ama1(modn)n(a)m(a)。例4若(m,n)=1，(a,mn)=1，则mn(a)=[m(a),n(a)]。(9)解记=mn(a)，=[m(a),n(a)]，由例3有m(a)，n(a)。(10)又由a1(modm)，a1(modn)得到a1(modmn)。因此，由定理2，有。由此及式(10)推出式(9)。例５若(m,n)=1，a1，a2是任意整数，(a1,m)=(a2,n)=1，则存在整数a，(a,mn)=1，使得mn(a)=[m(a1),n(a2)]。解设方程组)(mod)(mod21naxmax的解是xa(modmn)，则(a,mn)=1，并且由例４可知mn(a)=[m(a),n(a)]=[m(a1),n(a2)]。习题一1.写出模11的指数表。1582.求模14的全部原根。3.设m1，模m有原根，d是(m)的任一个正因数，证明：在模m的简化剩余系中，恰有(d)个指数为d的整数，并由此推出模m的简化剩余系中恰有((m))个原根。4.设m3，g是模m的原根，x1,x2,,x(m)是模m的简化剩余系，证明：(ⅰ)2)(mg1(modm)；(ⅱ)x1x2x(m)1(modm)。5.设p=2n1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根。6.证明：(ⅰ)设p奇素数，则Mp=2p1的素因数必为2pk1型；(ⅱ)设n0，则Fn=n221的素因数必为2n+1k1型。第二节原根对于什么样的正整数m，模m的原根是存在的？这是本节要研究的问题。为了叙述方便，对于正整数n，设它的标准分解式是n=kkppp21212，其中pi（1ik）是奇素数，记(n)=[)(,),(),(),2(2121kkppp]。定理1模m有原根的必要条件是m=1，2，4，p或2p，其中p是奇素数，1。证明若m不具备定理中所述形式，则必是m=2（3），(1)m=kkppp21212（2，k1），(2)或m=kkppp21212（0，k2），(3)159其中pi（1ik）是奇素数，i（1ik）是正整数。如果m是形如式(2)的数，那么对于任意的a，(a,m)=1，有，，，，，，kipaakipaaiiiiimmip1)(mod1)2(mod11)(mod1)2(mod1)()()()2(a(m)1(modm)。(4)容易验证(m)(m)。因此，由式(4)可知，任何与m互素的数a不是模m的原根。同样方法可以证明，若m是形如式(1)或式(3)中的数，模m也没有原根。证毕。下面我们要证明，定理1中的条件也是充分条件。为此，先要证明几个引理。引理1设m是正整数。对任意的整数a，b，一定存在整数c，使得m(c)=[m(a),m(b)]。证明由第一章第六节习题6，存在正整数1，2，1，2，使得m(a)=12，m(b)=12，(2,2)=1，[m(a),m(b)]=22。(5)由第一节定理3，有22)()(11bamm，，因此，由第一节定理4得到)()()(1111babammm=22=[m(a),m(b)]。取c=11ba即可得证。证毕。引理2若p是奇素数，则模p有原根。证明由引理1及归纳法容易证明，存在整数g，(g,p)=1，使得=p(g)=[p(1),p(2),,p(p1)]。显然p1，p(j)，1jp1。(6)另一方面，由式（6）可知同余方程160x10(modp)有解xi(modp)，1ip1。所以，由第五章第四节定理2，可知，p1。由此及式(6)，得到p1=，即g是模p的原根。证毕。引理3设p是奇素数，是正整数，则模p有原根。证明不妨设1。设g是模p的原根，则(g,p)=1。因此，存在整数x0，使得gp1=1px0，因此，对于任意的整数t，有(gpt)p1=gp1p(p1)tgp2=1p(x0gp2t)p2Q2，其中Q2Z，即(gpt)p11p(x0gp2t)(modp2)。(7)取t0=0，当p|x0；t0=1，当px0，则p|x0gp2t0=y0，于是(gpt0)p1=1+py01(modp2)，p|y0。(8)由式(8)，有(gpt0)p(p1)=(1py0)p=1p2y1，其中y1=y02Cpy02pp2y0py0(modp)。(9)因此，p|y1。类似地，由式(9)可以依次得到，，，111)1(03413)1(02312)1(01)1()(1)1()(1)1()(132ypypptgypypptgypypptgppppppppp(10)其中y1y2y0(modp)。因此p|yi，0i1。(11)由于g是模p的原根，所以gpt0也是模p的原根，设gpt0对模p的指数是，则有(gpt0)1(modp)，161(gpt0)1(modp)，因此，由指数的性质可知p(gpt0)，即p1。另一方面，由的定义及第一节定理2的推论，有(p)=p1(p1)，所以=pr1(p1)，1r，即)1(1)(pprptg1(modp)。（12）由式(10)，有)1(1)(pprptg=1pryr1，所以，由上式及式(12)推出1pryr11(modp)，pryr10(modp)。由此及式(11)得到r。所以r=，即gpt0是模p的原根。证毕。引理4设p是奇素数，1，则模2p有原根。证明设g是模p的原根，则gp也是模p的原根，以g1表示g与gp中的奇数，则)(1pg1(modp)，g11(mod2)，因为(2,p)=1，(p)=(2p)，所以)2(1pg1（mod2p）。（13）我们指出，不存在正整数r(2p)，使得g1r1(mod2p)。否则，由上式得到(g1,p)=1，g1r1(modp)，从而g1不能是模p的原根。以上证明了p2(g1)=(2p)，即g1是模2p的原根。证毕。定理2设p是奇素数，m=2，4，p，2p，则模m有原根。证明由引理3和引理4，只需证明模2与模4有原根，这容易验证：1是模2的原根，3是模4的原根。证毕。定理3设m1，(m)的所有不同的素因数是p1,p2,,pk，(g,m)=1，则g是模m的原根的充要条件是ipmg)(1(modm)，1ik。(14)162证明(ⅰ)必要性是显然的。(ⅱ)设式(14)成立。记=m(g)，由第一节定理2推论，有(m)。若(m)，则)(m1，所以，必有某个pi（1ik），使得pi)(|m，因此ipmigpm)()(|，1(modm)，这与式(14)矛盾。因此=(m)，即g是模m的原根。证毕。例1求模7的原根。解由第一节例题1可知模7有两个原根3和5。例2已知5是模23的原根，解同余方程x818(mod23)。(15)解由第一节定理1，5i(mod23)（i=0,1,2,,21）构成模23的简化系，列表为i0123456789105i(mod23)1521042