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

1、第七章 原 根原根是數(shù)論的理論和應(yīng)用中一個(gè)很重要的概念。本章要介紹原根以及與它有關(guān)的基本知識(shí)。第一節(jié) 指數(shù)及其基本性質(zhì)定義1 設(shè)m > 1，(a, m) = 1，則使a r º 1 (mod m) (1)成立的最小的正整數(shù)r，稱為a對(duì)模m的指數(shù)，記為dm(a)，在不致誤會(huì)的情況下，簡記為d(a)。由Euler定理，當(dāng)r = j(m)時(shí)式(1)成立，因此，恒有dm(a) £ j(m)。若a º b (mod m)，(a, m) = 1，則顯然有dm(a) = dm(b)。定義2 若dm(a) = j(m)，則稱a是模m的原根。例如，當(dāng)m = 7時(shí)，因?yàn)?1 &

2、#186; 2，22 º 4，23 º 1 (mod 7)，所以d7(2) = 3。又因?yàn)?1 º 3，32 º 2，33 º 6，34 º 4，35 º 5，36 º 1 (mod 7)，所以d7(3) = 6 = j(7)，3是模7的原根。以后，在談到a對(duì)模m的指數(shù)時(shí)，總假定m > 1，(a, m) = 1。定理1 記d = dm(a)，則a0, a1, L, a d - 1對(duì)模m兩兩不同余。證明 用反證法。若有0 £ i < j £ d - 1，使得a i º a j

3、 (mod m)，則由(a, m) = 1得到a j - i º 1 (mod m)，這與d = dm(a)的定義矛盾，所以定理成立。證畢。定理1說明，若g是模m的原根，則g0, g1, L, gj(m) - 1構(gòu)成模m的簡化剩余系。定理2 設(shè)d = dm(a)，r與r¢是正整數(shù)，則a r º a r ¢ (mod m) (2)的充要條件是r º r ¢ (mod d)。 (3)特別地，a r º 1 (mod m)的充要條件是d½r。證明 不妨設(shè)r > r¢。因?yàn)?a, m) = 1，所以式(2)

4、等價(jià)于a r - r ¢ º 1 (mod m)。 (4)若式(4)成立，記r - r ¢ = qd + t，qÎN，0 £ t < d，則由定義1，有a t º a qd + t = a r - r ¢ º 1 (mod m)。由dm(a)的定義可知t = 0，即d½r - r ¢，也即式(3)成立。必要性得證。若式(3)成立，則存在qÎN，使得r - r ¢ = qd，則由定義1，有a r - r ¢ = a qd º 1 (mod m)，即式(

5、4)成立，從而式(2)成立，充分性得證。取r ¢ = 0，得到定理的第二個(gè)結(jié)論。證畢。推論 dm(a)½j(m)。證明 由Euler定理及定理2得證。定理3 設(shè)k是非負(fù)整數(shù)，則。證明 記d = dm(a)，d ¢ = dm(ak)，d ¢¢ =，則由定理2及akd ¢¢ º 1 (mod m)可知d ¢½d ¢¢。 (5)由定理2及akd ¢ = (ak)d ¢ º 1 (mod m)可知d½kd ¢，因此d ¢&#

6、162; =。 (6)由于，所以由式(6)可以推出d ¢¢½d ¢。由此及式(5)得到d ¢¢ = d ¢。證畢。推論 若dm(a) = kl，k > 0，l > 0，則dm(ak) = l。定理4 等式dm(ab) = dm(a)dm(b) (7)與(dm(a), dm(b) = 1 (8)是等價(jià)的。證明 記d1 = dm(a)，d2 = dm(b)，d3 = dm(ab)，l = d1, d2。若式(7)成立，則l½d1d2 = d3。由l的定義和定理2，以及(ab)l = albl º

7、1 (mod m)又得到d3½l。因此d3 = l，即d1d2 = d1, d2，所以(d1, d2) = 1，即式(8)成立。若式(8)成立，則由定理2及1 º(mod m)得到d1½d2d3。由式(8)推出d1½d3。同理可推出d2½d3。所以l = d1, d2½d3。但是，由式(8)可知d1, d2 = d1d2，所以d1d2½d3。另一方面，由定理2及º 1 (mod m)得到d3½d1d2。所以d3 = d1d2，即式(7)成立。證畢。例1 求1，2，3，4，5，6對(duì)模7的指數(shù)。根據(jù)定義1直接

8、計(jì)算，得到d7(1) = 1，d7(2) = 3，d7(3) = 6，d7(4) = 3，d7(5) = 6，d7(6) = 2。例1中的結(jié)果可列表如下：a123456d7(a)136362這樣的表稱為指數(shù)表。這個(gè)表就是模7的指數(shù)表。下面是模10的指數(shù)表：a1379d10(a)1442例2 若(a, m) = 1，aa ¢ º 1 (mod m)，則dm(a) = dm(a ¢)。解 顯然(a ¢, m) = 1。要證明的結(jié)論由a d º 1 (mod m) Û (a ¢) d º 1 (mod m)即可得出。例3

9、 若n½m，則dn(a)½dm(a)。解 由n½m及定理2有º 1 (mod m) Þº 1 (mod n) Þ dn(a)½dm(a)。例4 若(m, n) = 1，(a, mn) = 1，則dmn(a) = dm(a), dn(a)。 (9)解 記d = dmn(a)，d ¢ = dm(a), dn(a)，由例3有dm(a)½d，dn(a)½d Þ d ¢½d。 (10)又由a d ¢ º 1 (mod m)，a d ¢

10、º 1 (mod n)得到a d ¢ º 1 (mod mn)。因此，由定理2，有d½d ¢。由此及式(10)推出式(9)。例 若(m, n) = 1，a1，a2是任意整數(shù)，(a1, m) = (a2, n) = 1，則存在整數(shù)a，(a, mn) = 1，使得dmn(a) = dm(a1), dn(a2)。解 設(shè)方程組的解是x º a (mod mn)，則(a, mn) = 1，并且由例可知dmn(a) = dm(a), dn(a) = dm(a1), dn(a2)。習(xí) 題 一1. 寫出模11的指數(shù)表。2. 求模14的全部原根。3.

11、設(shè)m > 1，模m有原根，d是j(m)的任一個(gè)正因數(shù)，證明：在模m的簡化剩余系中，恰有j(d)個(gè)指數(shù)為d的整數(shù)，并由此推出模m的簡化剩余系中恰有j(j(m)個(gè)原根。4. 設(shè)m ³ 3，g是模m的原根，x1, x2, L, xj(m)是模m的簡化剩余系，證明：() º -1 (mod m)；() x1x2Lxj(m) º -1 (mod m)。5. 設(shè)p = 2n + 1是一個(gè)奇素?cái)?shù)，證明：模p的全部二次非剩余就是模p的全部原根。6. 證明：() 設(shè)p奇素?cái)?shù)，則Mp = 2p - 1的素因數(shù)必為2pk + 1型；() 設(shè)n ³ 0，則Fn =+ 1的

12、素因數(shù)必為2n + 1k + 1型。第二節(jié) 原 根對(duì)于什么樣的正整數(shù)m，模m的原根是存在的？這是本節(jié)要研究的問題。為了敘述方便，對(duì)于正整數(shù)n，設(shè)它的標(biāo)準(zhǔn)分解式是n =，其中pi（1 £ i £ k）是奇素?cái)?shù)，記l(n) = 。定理1 模m有原根的必要條件是m = 1，2，4，pa或2pa，其中p是奇素?cái)?shù)，a ³ 1。證明 若m不具備定理中所述形式，則必是m = 2a（a ³ 3）， (1)m =（a ³ 2，k ³ 1）， (2)或m =（a ³ 0，k ³ 2）， (3)其中pi（1 £ i £

13、; k）是奇素?cái)?shù)，a i（1 £ i £ k）是正整數(shù)。如果m是形如式(2)的數(shù)，那么對(duì)于任意的a，(a, m) = 1，有al(m) º 1 (mod m)。 (4)容易驗(yàn)證l(m) < j(m)。因此，由式(4)可知，任何與m互素的數(shù)a不是模m的原根。同樣方法可以證明，若m是形如式(1)或式(3)中的數(shù)，模m也沒有原根。證畢。下面我們要證明，定理1中的條件也是充分條件。為此，先要證明幾個(gè)引理。引理1 設(shè)m是正整數(shù)。對(duì)任意的整數(shù)a，b，一定存在整數(shù)c，使得dm(c) = dm(a), dm(b)。證明 由第一章第六節(jié)習(xí)題6，存在正整數(shù)l1，l2，m1，m2

14、，使得dm(a) = l1l2，dm(b) = m1m2，(l2, m2) = 1，dm(a), dm (b) = l2m2 。 (5)由第一節(jié)定理3，有，因此，由第一節(jié)定理4得到= l2m2 = dm(a), dm(b)。取c =即可得證。證畢。引理2 若p是奇素?cái)?shù)，則模p有原根。證明 由引理1及歸納法容易證明，存在整數(shù)g，(g, p) = 1，使得d = dp(g) = dp(1), dp(2), L, dp(p - 1)。顯然d½p - 1，dp(j)½d，1 £ j £ p - 1。 (6)另一方面，由式（6）可知同余方程x d - 1 

15、6; 0 (mod p)有解x º i (mod p)，1 £ i £ p - 1。所以，由第五章第四節(jié)定理2，可知，p - 1 £ d。由此及式(6)，得到p - 1 = d，即g是模p的原根。證畢。引理3 設(shè)p是奇素?cái)?shù)，a是正整數(shù)，則模pa有原根。證明 不妨設(shè)a > 1。設(shè)g是模p的原根，則(g, p) = 1。因此，存在整數(shù)x0，使得gp - 1 = 1 + px0 ，因此，對(duì)于任意的整數(shù)t，有(g + pt) p - 1 = g p - 1 + p(p - 1)tg p - 2 + L = 1 + p(x0 - g p - 2t) + p2

16、Q2，其中Q2ÎZ，即(g + pt) p - 1 º 1 + p(x0 - g p - 2t) (mod p2)。 (7)取t0 = 0， 當(dāng)px0；t0 = 1， 當(dāng)p½x0，則px0 - g p - 2t0 = y0，于是(g + pt0) p - 1 = 1 + py01 (mod p2)，py0。 (8)由式(8)，有(g + pt0) p(p - 1) = (1 + py0)p = 1 + p2y1，其中y1 = y0 +y02 + L + pp - 2 y0p º y0 (mod p)。 (9)因此，py1。類似地，由式(9)可以依次得到

17、(10)其中ya - 1 º ya - 2 º L º y0 (mod p)。因此pyi，0 £ i £ a - 1。 (11)由于g是模p的原根，所以g + pt0也是模p的原根，設(shè)g + pt0對(duì)模pa的指數(shù)是d，則有(g + pt0)d º 1 (mod pa)，(g + pt0)d º 1 (mod p)，因此，由指數(shù)的性質(zhì)可知dp(g + pt0)½d，即p - 1½d。另一方面，由d的定義及第一節(jié)定理2的推論，有d½j(pa) = pa - 1(p - 1)，所以d = pr - 1

18、(p - 1)，1 £ r £ a，即º 1 (mod pa)。 （12）由式(10)，有= 1 + pryr - 1 ，所以，由上式及式(12)推出1 + pryr - 1 º 1 (mod pa)，pryr - 1 º 0 (mod pa)。由此及式(11)得到r ³ a。所以r = a，即g + pt0是模pa的原根。證畢。引理4 設(shè)p是奇素?cái)?shù)，a ³ 1，則模2pa有原根。證明 設(shè)g是模pa的原根，則g + pa也是模pa的原根，以g1表示g與g + pa中的奇數(shù)，則º 1 (mod pa)，g1 

19、6; 1 (mod 2)，因?yàn)?2, p) = 1，j(pa) = j(2pa)，所以º 1（mod 2pa）。 （13）我們指出，不存在正整數(shù)r < j(2pa)，使得g1r º 1 (mod 2pa)。否則，由上式得到(g1, pa) = 1，g1r º 1 (mod pa)，從而g1不能是模pa的原根。以上證明了(g1) = j(2pa)，即g1是模2pa的原根。證畢。定理2 設(shè)p是奇素?cái)?shù)，m = 2，4，pa，2pa，則模m有原根。證明 由引理3和引理4，只需證明模2與模4有原根，這容易驗(yàn)證：1是模2的原根，3是模4的原根。證畢。定理3 設(shè)m >

20、; 1，j(m)的所有不同的素因數(shù)是p1, p2, L, pk，(g, m) = 1，則g是模m的原根的充要條件是1 (mod m)，1 £ i £ k。 (14)證明 () 必要性是顯然的。() 設(shè)式(14)成立。記d = dm(g)，由第一節(jié)定理2推論，有dïj(m)。若d < j(m)，則> 1，所以，必有某個(gè)pi（1 £ i £ k），使得pi，因此dº 1 (mod m)，這與式(14)矛盾。因此d = j(m)，即g是模m的原根。證畢。例1 求模7的原根。解 由第一節(jié)例題1可知模7有兩個(gè)原根3和5。例2 已知5是模23的原根，解同余方程x8 º 18 (mod 23)。 (15)解 由第一節(jié)定理1，5i (mod 23)（i = 0, 1, 2, L, 21）構(gòu)成模23的簡化系，列表為i 0 1 2 3 4 5 6 7 8 9 105i (mod 23) 1 5 2 10 4 20 8 17 16 11 9i 11 12 13 14 15 16 17 18 19 20 215i (mod 23) 22 18 21 13 19 3 15 6 7 12 14由上表可知512 º 18 (mod 23)。設(shè)x º 5 y (mod 2