初等数论第七章原根

初等数论第七章原根初等数论第七章原根初等数论第七章原根初等数论第七章原根PAGEPAGE158PAGEPAGE157第七章原根原根是数论的理论和应用中一个很重要的概念.本章要介绍原根以及与它有关的基本知识。第一节指数及其基本性质定义1设m>1（,)=1，则使成立的最小的正整数am的指数，记为

ar 1(mod（a)，在不致误会的情况下，简记为m

（a）.

（1)由Euler定理，当r= 时式(1)成立，因,恒

m若a b(mod=1，则显然

（a)=m

(。m定义2若

()= （，则称a是模m的原根。m例如,当m=7时，因为21 2，22 4，23 1(mod7）,所以 （2)=3。又因为731 3,32 2,33 6，34 4，35 5，36 1（mod7)，所以 （3)=6= （7)，3是模7的原.7a对模mm〉,=1。定理1记 =m两两不同余。

(a）,则m

,a 1证明用反证法。若有0 i<j 1，使得ai aj(mod，则由(a,m）=1得到aj i 1（mod，这与 =

（a）的定义矛盾，所以定理成立。证毕。m1g是模m的原根,则m的简化剩余系。

,g（m) 1定理2设 的充要条件是

(，r与rm

ar ar （modr r （mod ).

（2)（3)特别地，ar 1(mod的充要条件是 证明不妨设r>r，)=1(2）等价于ar r 1(mod。 若式（4）成立,记r r =q N，0 t〈 ，则由定义1，有at aq t=ar r 1（mod由 的定义可知t=0,即 r r也即式(3）成立。必要性得证。若式(3）成立，则存在q若式(3）成立，则存在qN,使得rr=q,则由定义1,有arr =aq1（modm）,即式（4）成立,从而式成立，充分性得证。取r =0，得到定理的第二个结论。证推论 m证明由Euler23设k是非负整数，则

(ak)

(a)m 。m m

(a),k)证明记

（a)，

= （， = ,则由定理2及m m ,k)1(mod可知

。 （5）由定理2及=1（mod可知 k ,因此= |k 。 (6）由于( ,k

k,,k

,k) ,k))1，所以由式（6)可以推出 由此及式(5）得到 =

.证毕。推论若

〉0，l>0，m

（ak)=l。m定理4等式与

（ab）=m

（a)m

(b)m

（7）是等价的。

（ m

=1 (8)m证明记 1

(， m 2

m 3

（a， =［ ， 。m 1 2若式(7)成立，则

= 2,以及1 2 3=ab 1（mod又得到3

。因此

= ，即3

=[ ,1 2 1

]，所以（ ,2 1

)=1,即式（8)成立.2若式（8)2

1 [(ab)3

3(ab)23

3a23

（modm)得到 。由式（8)推出1 2 3

.同理可推出1 3

.所以2 3但是,由式（8）可[ , ]=1 2

=［ ， ] 。1 2 3，所以1 2。2

1(ab)1

1 2 321(modm）2得到 。所以 =3 1 2 3

，即式(7）成立。证毕。1 211，2，3,4,5，67根据定义1直接计算,得到1

(1）=1，7(4)=3,7

（2）=3，7（5)=6，7

(3）=6,7(6)=2。7123456136362a（a（a）7aa（a)1011347492例2若，)=，aa 1（mod，则解显然（a

(a)=m，m）=1。要证明的结论由

（a）.mad 1（mod(a）d 1(mod即可得出。3若n

n

(。m解由nm2am

1(moda

(a)

1(modn）

（a）n

(a)。mm例4，）=1（，m)=，则m

（a）=[mn

（a)，m

)。 (）n解记

=mn

，m

（a)]，由例3有n（a)m又由

, 。 （10）na 1（mod得到

1（modn）a 1(mod因此，由定理2，有 .由此及式（1）推出式（9。例５)=，a是任意整数，(a（a=，则存在整数=1 2 1得（a）=［

2(a),

(a。解设方程组

mn m 1 n 2xa

(modm) 1xa2(modn)的解是x a(modm，则（,m）=，并且由例４可知()=［ （）, ］=［ a), (a)].mn m n m 1 n 2习题一1。写出模11的指数表.14m〉1，模m有原根，d是的任一个正因数，证明：在模m个指数为d的整数,并由此推出模m的简化剩余系中恰有（（）

(d）设m 3，g是模m的原根,x,x, ，x 是模m的简化剩余系，证明：1 2(m)(ⅰ）g 2 1(mod；

（m)（ⅱ)xxx 1(mod12 （m)设p=2n 1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根.6。证明：（ⅰ）pMp

=2p

1的素因数必为2pk 1型；(ⅱ)设n 0，则Fn

=22n 1的素因数必为2n+1k 1型。第二节原根对于什么样的正整数m,模m的原根是存在的？这是本节要研究的问题。为了叙述方便，对于正整数n，设它的标准分解式是其中p(1 i 是奇素,记i

n=2 p11p

p22

pk，kp=［(2),( p11

),(p2

),,(pk)。k初等数论第七章原根初等数论第七章原根初等数论第七章原根初等数论第七章原根PAGEPAGE159PAGEPAGE158定理1模m有原根的必要条件是m=1，2，4，p或2p，其中p是奇素数， 1证明若m不具备定理中所述形,则必是m=2( 3)， （1）pm=2 p11或

p22

pk(k

2，k ， （）pm=2 p11

p22

pkk

，k 2， （3)其中p（1 i 是奇素数，i

(1 i 是正整数。i如果m(2)的数，那么对于任意的，)=1，有a()(od2)，a(pi)1(modp)，1ik，i iia(m)1(mod2)，a(m)(odpi)，1i，i容易验证

a(） 1(mod。)<

（4）因此，由式(4)可知，任何与ma不是模m的原根.同样方法可以证明，若m是形如式（1)或式（3）中的数，模m也没有原根。证毕。下面我们要证明，定理1中的条件也是充分条件。为此，先要证明几个引理。1设m是正整数。对任意的整数，一定存在整数（c)=［m

(a),m

（b)]。m证明由第一章第六节习题6，存在正整数 ， 1 2

， ，使得1 2(a）=m

, 1 2 m

（ 1 2 2

)=1，2由第一节定理3，有

[ m

)]= 。m 2 2

(5)4

(a1m1

)，2

(b

),121 (ab

)

(a

(b)=

=[

（b)].2 mmcab2 mm

1 1 1 1m m m即可得证.证毕。1 12若p是奇素数，则模p有原根。证明由引理1及归纳法容易证明，存在整数（，)=1,使得= =[p显然

(1),p

（2， ，p

(p 1）]。p另一方面，由式（6）可知同余方程

p

，1 j p 1.p

（6)x 1 0(mod有解x i(modi p 1。所以，由第五章第四节定理2，可知，p 1（6)，得到p 1= ，即g是模p的原根。证毕。3设p是奇素数，是正整数，则模p有原根。证明不妨设 >1。设g是模p的原根，=1.因此，存在整数x，使得0

。由此及式因此，对于任意的整数t，有

1=1 px，0(g p 1=gp 1 1）tgp 2 =1 0

gp

,2其中Q2取

Z，即

(g p）p 1 1 （x gp 2)(mod2。0

（7）t=0，p|x;0 0t=1，当px,0 0p|x0

gp 2t0

=y于是，0，

（g pt)p 1=1+

1（mod2，p|y。 (8)由式（8，有其中

(g pt）1）=(10

0py）p=10

0 0，1y=y

C2y

2yp

(mod。 (9)1 0 p 0 0 0因此，p|y。类似地，由式（9）可以依次得到1

(gpt)p2(0

p2y)p1p3y ，1 2(gpt0

)p3(

(1p3y1

)p1p4y，3

(10)其中y y1 2

y（mod0

(gpt0

)p1(p)1p1y1

)p1py

1，ipy，0 i 。 (11)i由于g是模p的原根，所以g pt0

也是模p的原根，设g pt0

对模p的指数是，则有因此,由指数的性质可知

(g pt） 1(modp)，0(g pt） 1(mod0(g pt） ，即p 1 。另一方面，由的定义及第一节定理2的推论，p 0有 （p）=p即由式(10，有

1(p 1),所以=1(p 1),1 r ,(gpt)pr1(p1) 1（modp)。 （12）r1所以，由上式及式（12）推出r1

(gpt)pr1(p1)=1 ，1 r 1pryr 1

1（modp),0（modp）.由此及式(11)得到r 。所以r= ，即g pt0

是模p的原根。证毕。引理4设p是奇素数， 1,则模2p有原根.证明设g是模p的原根，则g p也是模p的原根，以g1

表示g与g p中的奇数，则g1

1(modp）,g1

1（mod2）,因为(2,)=，(p)= (2p，所以

g1(mod2p）. （13）1我们指出，不存在正整数r〈否则,由上式得到

（2p)，使得gr 1（mod2p。1（g,p）=1,gr 1（modp),从而g1

1 1不能是模p的原根。以上证明了

(g）= （2p，即

是模2p的原根.证毕.2p 1 12设p是奇素数，m=2,4，p，2p，则模m有原根。证明32424证毕。定理3设m〉1，的所有不同的素因数是p,p, ,p=则g是模m的原根的充要条件是

1 2 k(m)(m)

1(mod

i (14）证明(ⅰ）必要性是显然的。（ⅱ)设式（14)成立。记

= 2m

（.若〈 （则(m)>1，所以,必有某个p（1 ii

pi|(m)

|(m),因此(m)p ，g pii

1（modm),这与式(14）矛盾.因此 = 即g是模m的原根。证毕。例1求模7的原根。解1735。例2已知5是模23的原根，解同余方程i5ii5i23）i5i23)0101911212214

18(mod23）. (15)（mod23)（i=0,1,2, ，21)2312345678952104208171611121314151617181920182113193156712由上表可知512设x 5

18(mod2。（mod23)，0 y

22，则由第一节定理2，方程(15）等价于8y 12(mod22). 因为(8，22）=212,所以方程（16)有两个解：因此,方程（15）有两个解

y 7，y1 2

18（mod22）.x 57 17，x1

518 6（mod23)。注：若模m有原根则模m的简化剩余系A={a,a, ,a｝与集合B={i }1 2 (m