初等数论 第七章 原 根

第七章  原 根 原根是数论的理论和应用中一个很重要的概念。本章要介绍原根以及与它有关的基本知识。 第一节  指数及其基本性质 定义1  设m > 1，(a, m) = 1，则使 a r 1 (mod m)                      (1) 成立的最小的正整数r，称为a对模m的指数，记为m(a)，在不致误会的情况下，简记为(a)。 由Euler定理，当r = (m)时式(1)成立，因此，恒有m(a) (m)。 若a b (mod m)，(a, m) = 1，则显然有m(a) = m(b)。 定义2  若m(a) = (m)，则称a是模m的原根。 例如，当m = 7时，因为 21 2，22 4，23 1 (mod 7)， 所以7(2) = 3。又因为 31 3，32 2，33 6，34 4，35 5，36 1 (mod 7)， 所以7(3) = 6 = (7)，3是模7的原根。 以后，在谈到a对模m的指数时，总假定m > 1，(a, m) = 1。 定理1  记 = m(a)，则 a0, a1, , a 1 对模m两两不同余。 证明  用反证法。若有0 i < j 1，使得 a i a j (mod m)， 则由(a, m) = 1得到 a j i 1 (mod m)， 这与 = m(a)的定义矛盾，所以定理成立。证毕。 定理1说明，若g是模m的原根，则 g0, g1, , g(m) 1 构成模m的简化剩余系。 定理2  设 = m(a)，r与r是正整数，则 a r a r (mod m)                      (2) 的充要条件是 r r (mod )。                    (3) 特别地，a r 1 (mod m)的充要条件是r。 证明  不妨设r > r。因为(a, m) = 1，所以式(2)等价于 a r r 1 (mod m)。                  (4) 若式(4)成立，记r r = q t，qN，0 t < ，则由定义1，有 a t a q t = a r r 1 (mod m)。 由m(a)的定义可知t = 0，即r r ，也即式(3)成立。必要性得证。 若式(3)成立，则存在qN，使得r r = q，则由定义1，有 a r r = a q 1 (mod m)， 即式(4)成立，从而式(2)成立，充分性得证。 取r = 0，得到定理的第二个结论。证毕。 推论  m(a)(m)。 证明  由Euler定理及定理2得证。 定理3  设k是非负整数，则 。 证明  记 = m(a)， = m(ak)， = ，则由定理2及 ak 1 (mod m) 可知 。                        (5) 由定理2及ak = (ak) 1 (mod m)可知k ，因此 = 。                  (6) 由于 ，所以由式(6)可以推出 。由此及式(5)得到 = 。证毕。 推论 若m(a) = kl，k > 0，l > 0，则m(ak) = l。 定理4  等式 m(ab) = m(a)m(b)                    (7) 与 (m(a), m(b)) = 1                      (8) 是等价的。 证明  记1 = m(a)，2 = m(b)，3 = m(ab)， = [1, 2]。 若式(7)成立，则12 = 3。由的定义和定理2，以及 (ab) = ab 1 (mod m) 又得到3。因此3 = ，即12 = [1, 2]，所以(1, 2) = 1，即式(8)成立。 若式(8)成立，则由定理2及 1 (mod m) 得到123。由式(8)推出13。同理可推出23。所以 = [1, 2]3。 但是，由式(8)可知[1, 2] = 12，所以 123。 另一方面，由定理2及 1 (mod m) 得到312。所以3 = 12，即式(7)成立。证毕。 例1  求1，2，3，4，5，6对模7的指数。 根据定义1直接计算，得到 7(1) = 1，7(2) = 3，7(3) = 6， 7(4) = 3，7(5) = 6，7(6) = 2。 例1中的结果可列 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 如下： a 1 2 3 4 5 6 7(a) 1 3 6 3 6 2               这样的表称为指数表。这个表就是模7的指数表。 下面是模10的指数表： a 1 3 7 9 10(a) 1 4 4 2           例2  若(a, m) = 1，aa 1 (mod m)，则 m(a) = m(a )。 解  显然(a , m) = 1。要证明的结论由 a d 1 (mod m) (a ) d 1 (mod m) 即可得出。 例3  若nm，则n(a)m(a)。 解  由nm及定理2有 1 (mod m) 1 (mod n) n(a)m(a)。 例4  若(m, n) = 1，(a, mn) = 1，则 mn(a) = [m(a), n(a)]。                  (9) 解  记 = mn(a)， = [m(a), n(a)]，由例3有 m(a)，n(a) 。            (10) 又由 a 1 (mod m)，a 1 (mod n) 得到 a 1 (mod mn)。 因此，由定理2，有 。由此及式(10)推出式(9)。 例５  若(m, n) = 1，a1，a2是任意整数，(a1, m) = (a2, n) = 1，则存在整数a，(a, mn) = 1，使得 mn(a) = [m(a1), n(a2)]。 解  设方程组 的解是x a (mod mn)，则(a, mn) = 1，并且由例４可知 mn(a) = [m(a), n(a)] = [m(a1), n(a2)]。 习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 一 1.  写出模11的指数表。 2.  求模14的全部原根。 3.  设m > 1，模m有原根，d是(m)的任一个正因数，证明：在模m的简化剩余系中，恰有(d)个指数为d的整数，并由此推出模m的简化剩余系中恰有((m))个原根。 4.  设m 3，g是模m的原根，x1, x2, , x(m)是模m的简化剩余系，证明： (ⅰ)  1 (mod m)； (ⅱ)  x1x2x(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）是奇素数，记 (n) = [ ]。 定理1  模m有原根的必要条件是m = 1，2，4，p或2p，其中p是奇素数， 1。 证明  若m不具备定理中所述形式，则必是 m = 2（ 3），                    (1) m = （ 2，k 1），            (2) 或 m = （ 0，k 2），        (3) 其中pi（1 i k）是奇素数， i（1 i k）是正整数。 如果m是形如式(2)的数，那么对于任意的a，(a, m) = 1，有 a(m) 1 (mod m)。                    (4) 容易验证 (m) < (m)。 因此，由式(4)可知，任何与m互素的数a不是模m的原根。 同样方法可以证明，若m是形如式(1)或式(3)中的数，模m也没有原根。证毕。 下面我们要证明，定理1中的条件也是充分条件。为此，先要证明几个引理。 引理1  设m是正整数。对任意的整数a，b，一定存在整数c，使得 m(c) = [m(a), m(b)]。 证明  由第一章第六节习题6，存在正整数1，2，1，2，使得 m(a) = 12，m(b) = 12，(2, 2) = 1， [m(a), m (b)] = 22 。                  (5) 由第一节定理3，有 ， 因此，由第一节定理4得到 = 22 = [m(a), m(b)]。 取c = 即可得证。证毕。 引理2  若p是奇素数，则模p有原根。 证明  由引理1及归纳法容易证明，存在整数g，(g, p) = 1，使得 = p(g) = [p(1), p(2), , p(p 1)]。 显然 p 1，p(j)，1 j p 1。              (6) 另一方面，由式（6）可知同余方程 x 1 0 (mod p) 有解x i (mod p)，1 i p 1。所以，由第五章第四节定理2，可知，p 1 。由此及式(6)，得到p 1 = ，即g是模p的原根。证毕。 引理3  设p是奇素数，是正整数，则模p有原根。 证明  不妨设 > 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 = 1 p(x0 g p 2t) p2Q2， 其中Q2Z，即 (g pt) p 1 1 p(x0 g p 2t) (mod p2)。          (7) 取 t0 = 0， 当p x0； t0 = 1， 当px0， 则p x0 g p 2t0 = y0，于是 (g pt0) p 1 = 1 + py0 1 (mod p2)，p y0。      (8) 由式(8)，有 (g pt0) p(p 1) = (1 py0)p = 1 p2y1， 其中 y1 = y0 y02 pp 2 y0p y0 (mod p)。        (9) 因此，p y1。类似地，由式(9)可以依次得到 (10) 其中y 1 y 2 y0 (mod p)。因此 p yi，0 i 1。                (11) 由于g是模p的原根，所以g pt0也是模p的原根，设g pt0对模p的指数是，则有 (g pt0) 1 (mod p)， (g pt0) 1 (mod p)， 因此，由指数的性质可知p(g pt0)，即p 1。另一方面，由的定义及第一节定理2的推论，有(p) = p 1(p 1)，所以 = pr 1(p 1)，1 r ， 即 1 (mod p)。        （12） 由式(10)，有 = 1 pryr 1 ， 所以，由上式及式(12)推出 1 pryr 1 1 (mod p)， pryr 1 0 (mod p)。 由此及式(11)得到r 。所以r = ，即g pt0是模p的原根。证毕。 引理4  设p是奇素数， 1，则模2p有原根。 证明  设g是模p的原根，则g p也是模p的原根，以g1表示g与g p中的奇数，则 1 (mod p)，g1 1 (mod 2)， 因为(2, p) = 1，(p) = (2p)，所以 1（mod 2p）。            （13） 我们指出，不存在正整数r < (2p)，使得 g1r 1 (mod 2p)。 否则，由上式得到 (g1, p) = 1，g1r 1 (mod p)， 从而g1不能是模p的原根。 以上证明了 (g1) = (2p)，即g1是模2p的原根。证毕。 定理2  设p是奇素数，m = 2，4，p，2p，则模m有原根。 证明  由引理3和引理4，只需证明模2与模4有原根，这容易验证：1是模2的原根，3是模4的原根。证毕。 定理3  设m > 1，(m)的所有不同的素因数是p1, p2, , pk，(g, m) = 1，则g是模m的原根的充要条件是 1 (mod m)，1 i k。            (14) 证明  (ⅰ)  必要性是显然的。 (ⅱ)  设式(14)成立。记 = m(g)，由第一节定理2推论，有(m)。若 < (m)，则 > 1，所以，必有某个pi（1 i k），使得pi ，因此 1 (mod m)， 这与式(14)矛盾。因此 = (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, , 21）构成模23的简化系，列表为 i 0 1 2 3 4 5 6 7 8 9 10 5i (mod 23) 1 5 2 10 4 20 8 17 16 11 9 i 11 12 13 14 15 16 17 18 19 20 21 5i (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, , a(m)}与集合B = { gi；1 i (m) }有一个一一对应关系，即，对于任意的a0A，存在唯一的gi0B，使得a0 gi0 (mod m)。此时，称i0是a0对模m的以g为底的指标，记为i0 = indga0 。从例2看出，利用指标的概念，我们可以将求解指数同余方程xn a (mod m)的问题转化为求解线性同余方程nindgx indga (mod (m))。 习 题 二 1.  求模29的最小正原根。 2.  分别求模293和模2293的原根。 3.  解同余方程：x12 16 (mod 17)。 4.  设p和q = 4p 1都是素数，证明：2是模q的一个原根。 5.  设m 3，g1和g2都是模m的原根，则g = g1g2不是模m的原根。 6.  设p是奇素数，证明：当且仅当p 1 n时，有 1n 2n (p 1)n 0 (mod p)。