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

1、第七章 原 根原根是数论的理论和应用中一个很重要的概念。本章要介绍原根以及与它有关的基本知识。第一节 指数及其基本性质定义1 设m > 1，(a, m) = 1，则使a r º 1 (mod m) (1)成立的最小的正整数r，称为a对模m的指数，记为dm(a)，在不致误会的情况下，简记为d(a)。由Euler定理，当r = j(m)时式(1)成立，因此，恒有dm(a) £ j(m)。若a º b (mod m)，(a, m) = 1，则显然有dm(a) = dm(b)。定义2 若dm(a) = j(m)，则称a是模m的原根。例如，当m = 7时，因为21 &

2、#186; 2，22 º 4，23 º 1 (mod 7)，所以d7(2) = 3。又因为31 º 3，32 º 2，33 º 6，34 º 4，35 º 5，36 º 1 (mod 7)，所以d7(3) = 6 = j(7)，3是模7的原根。以后，在谈到a对模m的指数时，总假定m > 1，(a, m) = 1。定理1 记d = dm(a)，则a0, a1, L, a d - 1对模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构成模m的简化剩余系。定理2 设d = dm(a)，r与r¢是正整数，则a r º a r ¢ (mod m) (2)的充要条件是r º r ¢ (mod d)。 (3)特别地，a r º 1 (mod m)的充要条件是d½r。证明 不妨设r > r¢。因为(a, m) = 1，所以

4、式(2)等价于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，得到定理的第二个结论。证毕。推论 dm(a)½j(m)。证明 由Euler定理及定理2得证。定理3 设k是非负整数，则。证明 记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、¢¢ =。 (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)是等价的。证明 记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对模7的指数

8、。根据定义1直接计算，得到d7(1) = 1，d7(2) = 3，d7(3) = 6，推荐精选d7(4) = 3，d7(5) = 6，d7(6) = 2。例1中的结果可列表如下：a123456d7(a)136362这样的表称为指数表。这个表就是模7的指数表。下面是模10的指数表：a1379d10(a)1442例2 若(a, m) = 1，aa ¢ º 1 (mod m)，则dm(a) = dm(a ¢)。解 显然(a ¢, m) = 1。要证明的结论由a d º 1 (mod m) Û (a ¢) d º 1 (m

9、od m)即可得出。例3 若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)

10、，a d ¢ º 1 (mod n)得到a d ¢ º 1 (mod mn)。因此，由定理2，有d½d ¢。由此及式(10)推出式(9)。例 若(m, n) = 1，a1，a2是任意整数，(a1, m) = (a2, n) = 1，则存在整数a，(a, mn) = 1，使得dmn(a) = dm(a1), dn(a2)。解 设方程组推荐精选的解是x º a (mod mn)，则(a, mn) = 1，并且由例可知dmn(a) = dm(a), dn(a) = dm(a1), dn(a2)。习 题 一1. 写出模11的指数表。

11、2. 求模14的全部原根。3. 设m > 1，模m有原根，d是j(m)的任一个正因数，证明：在模m的简化剩余系中，恰有j(d)个指数为d的整数，并由此推出模m的简化剩余系中恰有j(j(m)个原根。4. 设m ³ 3，g是模m的原根，x1, x2, L, xj(m)是模m的简化剩余系，证明：() º -1 (mod m)；() x1x2Lxj(m) º -1 (mod m)。5. 设p = 2n + 1是一个奇素数，证明：模p的全部二次非剩余就是模p的全部原根。6. 证明：() 设p奇素数，则Mp = 2p - 1的素因数必为2pk + 1型；() 设n &#

12、179; 0，则Fn =+ 1的素因数必为2n + 1k + 1型。第二节 原 根对于什么样的正整数m，模m的原根是存在的？这是本节要研究的问题。为了叙述方便，对于正整数n，设它的标准分解式是推荐精选n =，其中pi（1 £ i £ k）是奇素数，记l(n) = 。定理1 模m有原根的必要条件是m = 1，2，4，pa或2pa，其中p是奇素数，a ³ 1。证明 若m不具备定理中所述形式，则必是m = 2a（a ³ 3）， (1)m =（a ³ 2，k ³ 1）， (2)或m =（a ³ 0，k ³ 2）， (3)其

13、中pi（1 £ i £ k）是奇素数，a i（1 £ i £ k）是正整数。如果m是形如式(2)的数，那么对于任意的a，(a, m) = 1，有al(m) º 1 (mod m)。 (4)容易验证l(m) < j(m)。因此，由式(4)可知，任何与m互素的数a不是模m的原根。同样方法可以证明，若m是形如式(1)或式(3)中的数，模m也没有原根。证毕。下面我们要证明，定理1中的条件也是充分条件。为此，先要证明几个引理。引理1 设m是正整数。对任意的整数a，b，一定存在整数c，使得dm(c) = dm(a), dm(b)。证明 由第一章第六节

14、习题6，存在正整数l1，l2，m1，m2，使得dm(a) = l1l2，dm(b) = m1m2，(l2, m2) = 1，推荐精选dm(a), dm (b) = l2m2 。 (5)由第一节定理3，有，因此，由第一节定理4得到= l2m2 = dm(a), dm(b)。取c =即可得证。证毕。引理2 若p是奇素数，则模p有原根。证明 由引理1及归纳法容易证明，存在整数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)另一方面

15、，由式（6）可知同余方程x d - 1 º 0 (mod p)有解x º i (mod p)，1 £ i £ p - 1。所以，由第五章第四节定理2，可知，p - 1 £ d。由此及式(6)，得到p - 1 = d，即g是模p的原根。证毕。引理3 设p是奇素数，a是正整数，则模pa有原根。证明 不妨设a > 1。设g是模p的原根，则(g, p) = 1。因此，存在整数x0，使得gp - 1 = 1 + px0 ，因此，对于任意的整数t，有(g + pt) p - 1 = g p - 1 + p(p - 1)tg p - 2 + L = 1

16、 + p(x0 - g p - 2t) + p2Q2，其中Q2ÎZ，即(g + pt) p - 1 º 1 + p(x0 - g p - 2t) (mod p2)。 (7)取t0 = 0， 当px0；t0 = 1， 当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)

17、。 (9)因此，py1。类似地，由式(9)可以依次得到 (10)其中ya - 1 º ya - 2 º L º y0 (mod p)。因此pyi，0 £ i £ a - 1。 (11)由于g是模p的原根，所以g + pt0也是模p的原根，设g + pt0对模pa的指数是d，则有(g + pt0)d º 1 (mod pa)，(g + pt0)d º 1 (mod p)，因此，由指数的性质可知dp(g + pt0)½d，即p - 1½d。另一方面，由d的定义及第一节定理2的推论，有d½j(pa)

18、= pa - 1(p - 1)，所以d = pr - 1(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 设p是奇素数，a ³ 1，则模2pa有原根。推荐精选证明 设g是模pa的原根，则g + pa也是模pa的原根，以g1表示g与g + p

19、a中的奇数，则º 1 (mod pa)，g1 º 1 (mod 2)，因为(2, p) = 1，j(pa) = j(2pa)，所以º 1（mod 2pa）。 （13）我们指出，不存在正整数r < j(2pa)，使得g1r º 1 (mod 2pa)。否则，由上式得到(g1, pa) = 1，g1r º 1 (mod pa)，从而g1不能是模pa的原根。以上证明了(g1) = j(2pa)，即g1是模2pa的原根。证毕。定理2 设p是奇素数，m = 2，4，pa，2pa，则模m有原根。证明 由引理3和引理4，只需证明模2与模4有原根，这容易

20、验证：1是模2的原根，3是模4的原根。证毕。定理3 设m > 1，j(m)的所有不同的素因数是p1, p2, L, pk，(g, m) = 1，则g是模m的原根的充要条件是1 (mod m)，1 £ i £ k。 (14)证明 () 必要性是显然的。() 设式(14)成立。记d = dm(g)，由第一节定理2推论，有dïj(m)。若d < j(m)，则> 1，所以，必有某个pi（1 £ i £ k），使得pi，因此dº 1 (mod m)，这与式(14)矛盾。因此d = j(m)，即g是模m的原根。证毕。例1 求模7

21、的原根。解 由第一节例题1可知模7有两个原根3和5。例2 已知5是模23的原根，解同余方程推荐精选x8 º 18 (mod 23)。 (15)解 由第一节定理1，5i (mod 23)（i = 0, 1, 2, L, 21）构成模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)。设x º 5 y (mod 23)，0 £ y £ 22，