初等數(shù)論 第七章 原 根

第七章 原根原根是數(shù)論的理論和應(yīng)用中一個(gè)很重要的概念。本章要介紹原根以及與它有關(guān)的基本知識(shí)。第一節(jié)指數(shù)及其基本性質(zhì)定義1 設(shè)m>1，(a,m)=則使ar1(modm) (1)mam(a)，在不致誤m會(huì)的情況下，簡(jiǎn)記為(a)。mmEulerr=時(shí)式(1)mm

(m)。m若ab(modm)，(a,m)=1，則顯然有m

(a)=

。定義2 若m

(a)=(m)，則稱a是模m的原根。例如，當(dāng)m=7時(shí)，因?yàn)?212，224，231(mod7)，所以(2)=3。又因?yàn)?7313，322，336，344，355，361(mod7)，所以(3)=6=(7)，3是模7的原根。7以后，在談到a對(duì)模m的指數(shù)時(shí)，總假定m>1，(a,m)=1。m定理1 記=mm

a0,a1, ,a1證明用反證法。若有0i<j1，使得aiaj(modm)，則由(a,m)=1得到

aji1(modm)，m這與=m

的定義矛盾，所以定理成立。證畢。定理1說明，若g是模m的原根，則g0,g1, ,g(m)1構(gòu)成模m的簡(jiǎn)化剩余系。m定理2 設(shè)=m

(a)，r與r是正整數(shù)，則arar(modm) (2)的充要條件是

rr(mod。 (3)特別地，ar1(modm)的充要條件是r。證明不妨設(shè)r>r。因?yàn)?a,m)=1，所以式(2)等價(jià)于arr1(modm)。 (4)若式(4)rr=qt，qN，0t<1，有ataqt=arr1(modm)。m由(a)的定義可知t=0，即rr，也即式(3)成立。必要性得證。若式(3)成立，則存在qN，使得rr=q，則由定義1，有marr=aq1(modm)，即式(4)(2)成立，充分性得證。r=0m推論 。m證明由Euler定理及定理2得證定理3 設(shè)k是非負(fù)整數(shù)，則 (ak)

(a)m 。m m

(a),k)證明記=(a)，=(ak)，= ，則由定理2及m m ,k)ak1(modm)可知。 (5)由定理2及ak=(ak)1(modm)可知k，因此=

| k

。 (6),k) ,k)由于( , k )1，所以由(6)可以推。由此及(5)得,k) ,k)到=。證畢。推論若=kl，k>0，l>0，則=l。定理4 等式與是等價(jià)的。

=(7)=1 (8)證明記=(a)，=(b)，=(ab)，=[,]。1 m 2 m 3 m 1 2若式(7)成立，則=。由的定義和定理2，以及12 3(ab)=ab1(modm)又得到

=，即=[,]，所以(,)=1，即式(8)3成立。

3 12 1 2 1 2若式(8)成立，則由定理2及1[(ab)3]

(ab)2

a2

(modm)33得到。由式(8)推出。同理可推出。所以331 23 1 3 2 3=[,]。1 2 3但是，由式(8)可知[,]=，所以1 2 1

2。2

12 31(ab)21(modm)1得到。所以=，即式(7)成立。證畢。3 12 3 12例1 求1，2，3，4，5，6對(duì)模7的指數(shù)根據(jù)定義1直接計(jì)算，得到(1)=1，(2)=3，(3)=7 7 7(4)=3，(5)=6，(6)=2。7 7 77例1中的結(jié)果可列表如下：7a123456(a)136362這樣的表稱為指數(shù)表。這個(gè)表就是模7的指數(shù)表。下面是模10的指數(shù)表：aa10(a)11347492例2 若(a,m)=1，aa1(modm)，則m(a)=m(a)。解顯然(a,m)=1。要證明的結(jié)論由ad1(modm) (a)d1(modm)即可得出。例3 若nm，則解由nm及定理2有am(a)1(modm) am(a)1(modn) nama例4 若(m,n)=1，(a,mn)=則=[m(a),。 (9)解記=mn(a)，=[m(a),n(a)]，由例3有 。 (10)又由a1(modm)，a1(modn)得到a1(modmn)。因此，由定理2，有。由此及式(10)推出式(9)。例５若(m,n)=,m

,n)=1，則存1 2 1 2在整數(shù)a，(a,mn)=1，使得解設(shè)方程組

mn(a)=[m(a1),n(a2)]。xa

(modm)x

1a(modn)2的解是xa(modmn)，則(a,mn)=1，并且由例４可知=[m(a),n(a)]=),

)]。1 211的指數(shù)表。14的全部原根。m>m的任一個(gè)正因數(shù)，證明：在mdm個(gè)原根。)mm,x2,,m的簡(jiǎn)化剩余系，證明：)(m)(ⅰ) g 2 1(modm)；(ⅱ) x1x2x(m)1(modm)。p=2n1是一個(gè)奇素?cái)?shù)，證明：模pp的全部原根。證明：(ⅰ) pMp=2p12pk1型；n(ⅱ) n0F12n+1k1型。n第二節(jié)原根mm的問題。為了敘述方便，對(duì)于正整數(shù)n，設(shè)它的標(biāo)準(zhǔn)分解式是1n=2p11

p22

pk，ki其中p（1ik）是奇素?cái)?shù)，記i1(n)=[(2),(p11

),(p2

),,(pk)。k定理1 模m有原根的必要條件是m=1，2，4，p或其中p是奇素?cái)?shù)，1。證明若m不具備定理中所述形式，則必是m=（3， (1)m=2pp2p

（2k， (2)11 2 k或m=2pp2p

（0，k， (3)11 2 k其中p（1ik）是奇素?cái)?shù)，（1ik）是正整數(shù)。i i如果m是形如式(2)的數(shù)，那么對(duì)于任意的a，(a,m)=1，有a(2)a(pi)ai

2)，(modpi)，1i，ia(m)

2)，容易驗(yàn)證

a(m)(modpi)，1i，i1(modm)。 (4)(m)<(m)。因此，由式(4)可知，任何與m互素的數(shù)a不是模m的原根。m(1)(3)m有原根。證畢。下面我們要證明，定理1中的條件也是充分條件。為此，先要證明幾個(gè)引理。引理1 設(shè)m是正整數(shù)。對(duì)任意的整數(shù)a，b，一定存在整數(shù)c，使得mmm(c)=[(a),(b)]。mmm證明由第一章第六節(jié)習(xí)題6，存在正整數(shù)，，，，使得1 2 1 2(a)=，(b)=，(,)=1，m 12 m 12 2 2[(a), (b)]=。 (5)由第一節(jié)定理3，有

m m 22(a)， (b)，m 1 2 m 1 2因此，由第一節(jié)定理4得到 (ab

)

(a(b

)==[(a),

(b)]。m 1 1

m 1 m 1

22 m mcab

即可得證。證畢。1 1引理2 若p是奇素?cái)?shù)，則模p有原根。證明由引理1及歸納法容易證明，存在整數(shù)g，(g,p)=1，使得=(g)=[(1),(2),,(p1)]。p p p p顯然p1，jp1。 (6)p另一方面，由式（6）可知同余方程x10(modp)有解xi(modp)，1ip1。所以，由第五章第四節(jié)定理2，可知，p1。由此及(6)，得到p1=即g是模p的原根。證畢。引理3 設(shè)p是奇素?cái)?shù)是正整數(shù)，則模p有原根。證明不妨設(shè)>1。設(shè)g是模p的原根，則(g,p)=1。因此，存在整數(shù)x，使得0gp1=1px0，因此，對(duì)于任意的整數(shù)t，有2(gpt)p1=gp1p(p1)tgp2=1p(x0gp2t)p2Q，其中Q2Z，即2(gpt)p11p(x0gp2t)(modp2)。 (7)取t0=0，當(dāng)px；0t0=1，當(dāng)px，0則p|x0gp2t0=y0，于是由式(8)，有

gp0)p1=1+p01(modp2，p|0。 (8)(gpt0)p(p1)=(1py0)p=1p2y，1其中y1=y0C2y2pp2ypy0(modp)。 (9)p0 01因此，p|y。類似地，由式(9)可以依次得到1(gpt)p2(0

p2y)p1p3y ，1 2(gpt0

)p3(

(1p3y1

)p1p4y，3

(10)(gpt0)p1(p)1p11)p1py1，其中y1y2 y0(modp)。因此ipy，0i。 (11)igpgpt0pgpt0(gpt0)1(modp)，(gpt0)1(modp)，因此，由指數(shù)的性質(zhì)可知(gpt)，即p1。另一方面，由的p 0定義及第一節(jié)定理2的推論，有(p)=p1(p1)，所以=pr1(p1)，1r，即由式(10)，有

(gpt)pr1(p1(mod。 （12）r(gpt)pr1(p=1pr所以，由上式及式(12)推出1pryr11(mod0pryr10(mod。rr=g0

是模p的原根。證畢。引理4 設(shè)p是奇素?cái)?shù)1，則模有原根。證明設(shè)g是模p的原根，則gp也是模p的原根，以g1表示g與gp中的奇數(shù)，則g1(mod

1(mod2)，1 1因?yàn)?2,p)=1，(p)=(2p)，所以g(2p)（mod。 13）1我們指出，不存在正整數(shù)r<(2p)，使得gr1(mod2p)。1否則，由上式得到(g,p)=1，gr1(modp)，1 1從而g1不能是模p的原根。以上證明了 (g)=即

是模2p的原根。證畢。2p 1 1定理2 設(shè)p是奇素?cái)?shù)=則模m有原根。證明由引理3和引理4，只需證明模2與模4有原根，這容易驗(yàn)證：1是模2的原根，3是模4的原根。證畢。定理3 設(shè)m>的所有不同的素因數(shù)是

,p,,p，(g,m)=1gm的原根的充要條件是(m)

1 2 kg pi 1(modm，1i。 (14)證明(ⅰ) 必要性是顯然的。mⅱ) (14=2m。m若<m()>（1ip|(m)，因此|(m)|(m) p ，g pi

i i 1(modm)，i這與式(14)矛盾。因此=(m)，即g是模m的原根。證畢。例1 求模7的原根。解由第一節(jié)例題1可知模7有兩個(gè)原根3和5例2 已知5是模23的原根，解同余方程x818(mod。 (15)解由第一節(jié)定理1，5i(mod23)（i=0,1