初等数论 第七章原 根

第七章 原 根原根是数论的理论和应用中一个很重要的概念。本章要介绍原根以及与它有关的基本知识。第一节 指数及其基本性质定义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，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 r。因为(a, m) = 1，所以式(2)等价于a r - r 1 (mod m)。 (4)若式(4)成立，记r - r = qd + t，qN，0 t 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)成立，则ld1d2 = d3。由l的定义和定理2，以及(ab)l = albl 1 (mod m)又得到d3l。因此d3 = l，即d1d2 = d1, d2，所以(d1, d2) = 1，即式(8)成立。若式(8)成立，则由定理2及1 (mod m)得到d1d2d3。由式(8)推出d1d3。同理可推出d2d3。所以l = d1, d2d3。但是，由式(8)可知d1, d2 = d1d2，所以d1d2d3。另一方面，由定理2及 1 (mod m)得到d3d1d2。所以d3 = d1d2，即式(7)成立。证毕。例1 求1，2，3，4，5，6对模7的指数。根据定义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 (mod m)即可得出。例3 若nm，则dn(a)dm(a)。解 由nm及定理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 1 (mod n)得到a d 1 (mod mn)。因此，由定理2，有dd 。由此及式(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的指数表。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 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)其中pi（1 i k）是奇素数，a i（1 i k）是正整数。如果m是形如式(2)的数，那么对于任意的a，(a, m) = 1，有al(m) 1 (mod m)。 (4)容易验证l(m) 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 + p(x0 - g p - 2t) + p2Q2，其中Q2Z，即(g + pt) p - 1 1 + p(x0 - g p - 2t) (mod p2)。 (7)取t0 = 0， 当px0；t0 = 1， 当px0，则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)可以依次得到 (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 - 1d。另一方面，由d的定义及第一节定理2的推论，有dj(pa) = 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 + pa中的奇数，则 1 (mod pa)，g1 1 (mod 2)，因为(2, p) = 1，j(pa) = j(2pa)，所以 1（mod 2pa）。 （13）我们指出，不存在正整数r 1，j(m)的所有不同的素因数是p1, p2, L, pk，(g, m) = 1，则g是模m的原根的充要条件是1 (mod m)，1 i k。 (14)证明 () 必要性是显然的。() 设式(14)成立。记d = dm(g)，由第一节定理2推论，有dj(m)。若d 1，所以，必有某个pi（1 i k），使得pi，因此d 1 (mod m)，这与式(14)矛盾。因此d = j(m)，即g是模m的原根。证毕。例1 求模7的原根。解 由第一节例题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，则由第一节定理2，方程(15)等价于8y 12 (mod 22)。 (16)因为(8, 22) = 212，所以方程(16)有两个解：y1 7，y2 18 (mod 22)。因此，方程(15)有两个解x1 57 17， x2 518 6 (mod 23)。注：若模m有原根g，则模m的简化剩余系A = a1, a2, L, aj(m)与集合B = gi；1 i j(m) 有一个一一对应关系，即，对于任意的a0A，存在唯一的gi0B，使得a0 gi0 (mod m)。此时，称i0是a0对模m的以g为底的指标，记为i0 = indga0 。从例2看出，利用指标的概念，我们可以将求解指数同余方程xn a (mod m)的问题转化为求解线性同余方程nindgx