初等数论第三章同余

1、第三章 同 余 1 同余的概念及其基本性质 定义1设m Z，称之为模。若用m去除两个整数a与b所得的余数相同, 则称a, b对模m同余，记作：a b (mod m)；若所得的余数不同，则称a, b对模m 不同余，记作： a b(mod m)。 例如， 8 1(mod 7)，；所有偶数 a 0(mod 2)，所有奇数 a 1(mod 2)。 同余是整数之间的一种 关系，它具有下列性质 ： 1、a a(mod m)； (反身性) 2、若 a b (mod m)，则 b a (mod m);(对称性) 3、若 a b (mod m)，b c (mod m)，则 a c(mod m);(传递性) 故同

2、余关系是等价关系 。 定理1 整数a,b对模m同余的充分必要条件是m|(a b)，即卩a b mt， t Z。 证明 设 a mq1 r1， b mq2r2， 0 r1,r2m， 则a b(mod m) r1 r2 a bm(q1 q2)m|(ab)。 性质1 (1)若 ai bi (mod m)， a?b2 (mod m)，贝U aia?bib2(mod m)； (2) 若 a b c (mod m),贝U a c b (mod m)。 性质2若a1b1 (modm)，a2b2 (modm),贝U a1a2b1b2(mod m); 特别地，若 a b (mod m)，贝U ka kb (mo

3、d m)。 定理2 若A 1k B 1 k (mod m)， xi yi (mod m)， i 1,2, ,k， 则A 1 k x1 1 1k k xk k B 1k y1 1 1k k ykk (mod m)；特别地，若 ai bi (mod m)， i 0,1,2, ,n，则 n anx n1 an 1x a0 nn 1 bnxbn 1x b0 (mod m)。 性质3 若a a1d， b b1d， (d,m) 1， a b(mod m)， 则 a1 b1 (mod m)。 性质4(1)若a b (mod m), k 0,贝U ak bk(modmk); 若a b (mod m), d是a

4、, b及m的任一公因数，则 (mod m) d d d 性质5 右a b (mod mi), i 1,2, k,则a b (mod m!, m2, mk ) 反之亦然。 性质6 右a b (mod m), d | m, d 0,则a b (mod d) 性质7 右a b(mod m),贝U (a, m) (b, m), 因而右d能整除a,b及m两数 之一，则d必能整除a,b中的另一数。 例1求3406写成十进位数时的个位 数码。 解 事实上，只需求满足 3406 a (mod 10)， 0 a 9的数a 因为 32 91 (mod 10)，所以 3 406 ( 32 ) 203 ( 1)203

5、1 9 (mod 10), 即个位数码是9 例2证明：当n为奇数时，3| 2n 1,当n为偶数时，3 | 2n 1。 证明 因为 21 (mod 3),所以 2n 1( 1)n 1 (mod 3), 当 n为奇数时，2n1( 1)n1110 (mod 3),故 3|2n1, 当 n为偶数时，2n1( 1)n1112 (mod 3),故 3 12n1。 同余性质在算术中的一些应用。 一、检查因数的方法 1、一整数能被3 (或9)整除的充分必要条件是它的十进位数码之和能被 3 (或9)整除。 证明 只需讨论正整数即可。任取 a Z ，则 a 可以写成十进位的形式： a an10n an 110n

6、1 a0， 0 ai 10，于是，由 10 1 (mod 3) 可知 a an an 1 a0 (mod 3)，从而 3 |a 3 |an an 1 a0。 对于 9 同理可证。 2、设正整数 a a n 1000 n an 11000 n 1 a0， 0 ai 1000 ，则 7(或 11或13) |a的充分必要条件是 7 (或11或13) | (ao a?) (ai as )。 证明 因为 7X 11 x 13=1001。 例 3 a=5874192 能被 3 和 9 整除。 例 4 a=435693 能被 3 整除，但不能被 9 整除。 例5 a=637693能被7整除；a=能被13整除

7、。 二、弃九法 (验算整数计算结果的方法) 例6 设a=28997，b=39495, P=ab=15，检查计算是否正确。 解 令 a an10n n1 an 110 a0， 0 ai 10 b bm10m m1 bm 110m 1 b0， 0 bj 10 P cl10l cl 110l 1 c 0， 0 c k 10 nml 则 ( ai)( bj)ck (mod 9)(*) i 0 j 0 k 0 若(*)不成立，则Pmab,故在本题中，计算不正确。 注 (1) 若( *)不成立，则计算不正确；但否命题不成立。 (2) 利用同样的方法可以用来验证整数的加、减运算的正确性。 2 剩余类及完全剩

8、余系 定理1设m 0,则全体整数可分成 m个集合，记作：K,Ki, , Km 1，其 中Kr qm r |q Z, r 0,1, ,m 1,这些集合具有下列性 质： (1) 每个整数必包含在而且 仅在上述的一个集合中 ； (2) 两个整数同在一个集合的充分必要条件是对模 m同余。 证设a是任一整数，则必有 a mq ra，0 ra m， 于是由ra的存在性可知a g，由ra的唯一性可知a只能在 g中。 (2)设整数 a,b Kr，贝U a mq1 r，b mq2 r，故 a b (mod m)。 反之，若a b (mod m),则a, b必处于同一 K r中。 定义1定理仲的K0,K1, ,

9、Km 1称为模m的剩余类，一个剩余类 中的任一 数称为它同类数的剩余 。 若m个整数a0,a1, ,am 1中任何两个数都不在同 一剩余类，则a0,a1, ,am 1 称为模m的一个完全剩余系。 推论 m个整数作成模 m的一个完全剩余系的充分必要条件是它们对模m 两两不同余。 例如，下列序列都是模 m的完全剩余系: (1) 0,1,2, ,m 1;(最小非负完全剩余系) 0,m1, am a, ,(m 1)m (m 1); 0, m 1,( a 1) m a, ,( 1)m 1 m (m 1)； (4)当m为偶数时， 1 m m 1, 5 1,0,1, m , 1； 2 2 2 m m m 2

10、 1, ,1,0,1, 1,； 2 2 2 当m为奇数时， m 2 1 55 1,0,1, 5 1 1 。 2 (绝对最小完全剩余系) 定理2 设m Z ,(a,m)! b 乙 若 x通过模m的一个完全剩余系，则 ax b也通过模m的一个完全剩余系，即 若a0 ,a!, ,am勺是模m的完全剩余系， 则aao b, aai b, , aam 1 b也是模m的完全剩余系。 证 只需证明aao b,aa1 b, , aam 1 b两两不同余即可，采用 反证法。 设aai b aaj b (mod m) (i j)，贝U aai aaj (mod m)， 又(a, m) 1,于是 ai a j (m

11、od m) (i j),与已知矛盾， 故aa0 b, aa! b, , aam ! b也是模m的完全剩余系。 定理3 设mt,m2 Z , (m! ,m2) 1,而x , x2分别通过模mt, m2的完全剩 余系，则m2Xt m! x2也通过模m m2的完全剩余系。 证 因为X!, x2分别通过m!, m2个整数，所以m2X! mx通过m2个整数, 下证这m!m2个整数对模m! m2两两不同余。 设 m2x m!X2 m2X!” m!X2(mod mm2),其中 xj,为，X2，X2分别是 所 通过的完全剩余系中的 数，贝U m2x! m2x! (mod m!), m!x2 m!x2 (mod

12、 m2), 又(mm?) ! 故 x! x! (mod m!), x2 x2 (mod m2)，这说明 m2Xt m! x2 所通过的数两两不同余，因此，m2x! m!x2也通过模m!m2的完全剩余系。 例1设m 0(mod2), a1, ,am及b1, ,bm都是模m的完全剩余系，则 a b1, am bm不是模m的完全剩余系。 ,bm都是模m的完全剩余系， 所以 m ai m i m(m 1) m (mod m), m 同理b i 1 i 1 2 2 i 1 m m m_ 从而 佝 bi) ai m m bi 0 (mod m), i 1 i 1 i 122 m 若a b, ,am bm是

13、模m的完全剩余系， 则佝 i 1 因此, a1 b1, ,a mbm 不是模m的完全剩余系。 证：因为ai, ,am及b , m (mod m), bi) 对任何正整数 n， (mod m)，矛盾。 例2 证明 证： 考察i c, b 11 1 个数：1,11, 设b 1, c 111, k个1s个 1 设 m Z ，(a,m) ax b 1 (m 1)。 2 存在着仅有数字1,0组成的数a，使得n|a。 ,111，它们对模n至少有两个在同一同余 类中, n 1个 1 c (mod n)，则 n |(b c) 111 000 a。 k s个1 s个 0 1, b Z， x通过模m的一个完全剩余

14、系, 证 因为x通过模m的一个完全剩余系，所 以ax b通过模m的一个完全 剩余系，从而竺亠通过2,丄，匹J mm m m ax b 01 1 (m 1)。 2 3 简化剩余系与欧拉函数 定义1欧拉函数(a)是定义在正整数集上的 函数，它的值等于序列 0,1,2, ,a 1中与a互质的数的个数。 注 若a是质数，则 (a) a 1若a是合数，则 (a) a 1 定义2 如果一个模m的剩余类中的数与 m互质，则称它为一个与 模m互质 的剩余类 在与模m互质的全部剩余类中，从每一类各取一数所作 成的数的集合称为 模m的一个简化剩余系。 定理1模m的剩余类与模m互质的充分必要条件是 此类中有一数与m

15、互质。 因此，与模m互质的剩余类的个数为 (m)，模m的每一简化剩余系是由 与m互质 的(m)个对模m不同余的整数组成的。 证 设K0, K1, ,Km1是模m的全部剩余类，若Kr与模m互质，则(r, m) 1; 反之，若有 kr K r, (kr,m) 1,则对于 Kr 中任一数 kr qm kr，有(kr,m) 1, 即Kr与模m互质。 定理2 若a1, a2, , a (m)是(m)个与m互质的整数，并且两两 对模m不同余， 则a1, a2, a (m)是模m的一个简化剩余系。 定理3 若(a,m) 1, x通过模m的简化剩余系，则ax也通过模m的简化剩 余系。 证 ax通过(m)个整数

16、，而且由(a,m) 1, (x,m) 1可知 (ax,m) 1, 若ax axj (mod m) (i j),则 x Xj (mod m) (i j),与已知矛盾， 故ax通过模m的简化剩余系。 定理4 设m1, m2 Z , (m1, m2) 1,而x1, x2分别通过模m1, m2的简化剩 余系，则m2Xt m x2也通过模mm?的简化剩余系。 证 由上一节定理3可知，若x ,x2分别通过模m-m?的完全剩余系，则 m2X! m/2也通过模m! m2的完全剩余系。下证当Xt, x2分别通过 模, m2的简 化剩余系时，m2x. m.x2通过模m.m2的一个完全剩余系中一 切与m.m2互质的

17、 整数。 一方面，由(x., m.) (x2,m2) (m.,m2) 1 可知(mzX.m.) 1, (m. x2, m2) 1, 于是(m2x1m1 x2, m1)1，(m1 x2m2x1, m2)1,从而(m2x1m1 x2, m1 m2)1， 另一方面，由(m2Xt m1x2,m1m2) 1 可知(m2Xt m1x2,m1) (m! x2 m2X!, m2) 1, 于是(mzymj (m/?,%) 1,从而(xmj (x2, m2) 1 推论设mm?Z ,(m!,m2)1,贝U(mtm2)(mJ(m2) 证 由定理4可知，若x1 ,x2分别通过模mt, m2的简化剩余系，贝U m2x1

18、m1 x2 通过模mm?的简化剩余系，即m2Xt m1 x2通过 (mt m2)个整数。 另一方面， 由于x1通过(mJ个整数， x2通过 (m2)个整数, 因此， m2 x1m1 x 通过 (m1) (m2)个整数。故 (mm?) (mJ (m2)。 定理5 设 aP11 P22Pkk，则 (a) a 1 1 1 1 1 1 P1 P2 Pk 证先证 (P )P P S在模P的完全剩余系1,2, p中，与 P不互质 的数为p,2p, ,P b共有 P 1 个，故(p ) pP ! 因此，(a) (P1 1) (P22) (Pkk) (P11P11 1)(P21P22 1) (Pkk k1 Pk ) 1 1 1 a 1 1 1 。 P1 P2 Pk 4欧拉定理费马定理 定理1 (Euler) 设m Z, m 1, (a, m) 1,则 a (m)1 (mod m)。 证 设几，2, r (m)是模m的简化剩余系，贝U ar!, ar2, ,ar(m)也是模m的简 化剩余系，于是(arj(ar2) (ar(m) 亡r )(mod m), 即 a 5)(*2r (m)A2r (m) (modm),又(n ,m)(j,m) (r)，m)1, 故(rj2r (m), m) 1,从而 a (m) 1 (mod m) 推论(Fermat定理)若p是质数，则ap a (mod p) 证