第七章 原 根原根是数论的理论和应用中一个很重要的概念本章要介绍原根以及与它有关的基本知识第一节 指数及其基本性质定义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 < j d - 1，使得a i a j (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)的充要条件是dr证明 不妨设r > r因为(a, m) = 1，所以式(2)等价于a r - r 1 (mod m) (4)若式(4)成立，记r - r = qd + t，qN，0 t < d，则由定义1，有a t a qd + t = a r - r 1 (mod m)由dm(a)的定义可知t = 0，即dr - r ，也即式(3)成立必要性得证若式(3)成立，则存在qN，使得r - r = qd，则由定义1，有a r - r = a qd 1 (mod m)，即式(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)可知dkd ，因此d = (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)成立，则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, d2]d3但是，由式(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) < j(m)。
因此，由式(4)可知，任何与m互素的数a不是模m的原根同样方法可以证明，若m是形如式(1)或式(3)中的数，模m也没有原根下面我们要证明，定理1中的条件也是充分条件为此，先要证明几个引理引理1 设m是正整数对任意的整数a，b，一定存在整数c，使得dm(c) = [dm(a), dm(b)]证明 由第一章第六节习题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)]显然dp - 1，dp(j)d，1 j p - 1 (6)另一方面，由式（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 + 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，。