第三章 同 余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);(传递性) 故同余关系是等价关系 定理1 整数a,b对*m m同余的充分必要条件是m | (a b),即a b mt,t Z证明 设 amq1r1，bmq2r2，0r1, r2m，则 a b (mod m)r1 r2 abm(q1 q2 )m | (ab)性质 1 ⑴若aibi (mod m),a2b2 (mod m),贝U aia2bi b2 (mod m);(2)若 a b c (mod m),则 a c b (mod m)。
性质2若aibi (mod m),a2b2(mod m),贝Uaia2bib2(mod m);特别地，若 a b (mod m),则 ka kb (mod m)定理2 若 A i k B i k (mod m)， xi yi (mod m)， i i,2,, k，则 A i k xi i xkikB i k yii ykk (mod m)；特别地，若 ai bi (mod m), ikn nia0 bnx bn ixb0 (mod m)nnii 0,i,2,, n ，则 anxan ix性质3 若a aid, b bid, (d ,m) i, a b (mod m),则 ai bi (mod m)°性质4 ⑴若a b (mod m), k 0,则 ak bk(modmk);(2)若a b (mod m), d是a, b及m的任一公因数，则 — —(mod m)° d d d性质5 若a b (mod mi), i 1,2,, k,则 a b (mod [m1, m2, ,mk])反之亦然性质6 若a b (mod m), d | m, d 0,则 a b(modd)性质7 若a b(mod m),则 (a, m) (b, m),因而若d能整除a,b及m两数之一，则d必能整除a,b中的另一数。
例1求3406写成十进位数时的个位 数码解 事实上，只需求满足 3406 a (mod 10), 0 a 9的数a 因为 32 91 (mod10),所以 3 406 ( 32 ) 203( 1)2031 9 (mod 10),即个位数码是9例2证明：当n为奇数时，312n 1,当n为偶数时，3 12n 1证明 因为 2 1(mod3),所以 2n 1 ( 1) n 1 (mod 3), 当 n为奇数时，2n1( 1)n11 1 0 (mod 3),故 312n1,当 n为偶数时，2n1( 1)n11 1 2 (mod 3),故 3 12n1同余性质在算术中的一些应用一、检查因数的方法1、一整数能被3 (或9)整除的充分必要条件是它的十进位数码之和能被3 (或9)整除证明 只需讨论正整数即可任取 a Z ,则a可以写成十进位的形式:a an10n an 110n 1 a0， 0 ai 10，于是，由10 1 (mod 3)可知a a n an 1a0 (mod 3)，从而3 | a 3 | a n a n 1a0对于 9 同理可证2、设正整数a an1000nan 11000 n 1a0， 0 ai 1000 ，则7(或11 或 13) |a 的充分必要条件是7(或11 或 13) | (a0 a2) (a1 a3)。
证明 因为 7X 11 X 13=1001例 3 a=5874192 能被 3 和 9 整除例 4 a=435693 能被 3 整除，但不能被 9 整除例5 a=637693能被7整除；2=能被13整除二、弃九法 (验算整数计算结果的方法)例6 设a=28997, b=39495, P=ab=15,检查计算是否正确解 令 a an10n an 110n 1a0， 0 ai 10b bm10m bm 110m 1b0， 0 bj 10ll1P cl 10cl 1 10c0， 0 ck 10nml则( ai)( bj)ck (mod 9)(*)i0j0k0若(*)不成立，则Pw ab,故在本题中，计算不正确注 (1) 若( * )不成立，则计算不正确；但否命题不成立2) 利用同样的方法可以用来验证整数的加、减运算的正确性§ 2剩余类及完全剩余系定理1设m 0,则全体整数可分成 近集合，记作：KcKi, ,Km「其中Kr {qm r | q Z}, r 0,1, ,m 1,这些集合具有下列性 质：⑴每个整数必包含在而且仅在上述的一个集合中；(2)两个整数同在一个集合的充分必要条件是对模 m同余。
证 ⑴设a是任一整数，则必有 a mq ra, 0 ra m, 于是由ra的存在性可知a Kr ,由ra的唯一性可知 W能在Kr中aa(2)设整数 a, b Kr,则 a mqi r, b mq? r,故 a b (mod m)反之，若a b (mod m),则a, b必处于同一 Kr中定义1定理仲的Ko,Ki, , Km i称为模m的剩余类，一个剩余类 中的任一 数称为它同类数的剩余若m个整数ao,ai, ,am i中任何两个数都不在同 一剩余类，则a0,ai, ,ami 称为模m的一个完全剩余系推论 m个整数作成模m的一个完全剩余系的充分必要条件是它们对模m两两不同余例如，下列序列都是模 m的完全剩余系:⑴0,i,2, ,m i;(最小非负完全剩余系)⑵ 0,m i, , am a, , (m i)m (m i);⑶ 0, m i, ,( i)am a,,(i)m im (m i);(4)当m为偶数时，ii,o,i,mi； 2i,i,o,i,m / m i,—2 2当m为奇数时,i,o,i,(绝对最小完全剩余系)定理2 设m Z , (a,m) 1, b乙若x通过模m的一个完全剩余系，则 ax b也通过模m的一个完全剩余系，即 若a^a^ ,am 1是模m的完全剩余系， 则aao b, aai b, ,aam 1 b也是模m的完全剩余系。
证只需证明aa0 b, aa1 b, , aam 1 b两两不同余即可，采用反证法 设aai b aaj b (mod m) (i j),贝U aai aaj (mod m),又(a,m) 1,于是 ai aj (mod m) (i j),与已知矛盾，故aa0 b, aa1 b, , aam 1 b也是模m的完全剩余系定理3 设m1,m2 Z , (m1, m2) 1,而得，*2分别通过模m1,m2的完全剩 余系，则m2* m1X2也通过模m〔m2的完全剩余系证 因为X1,X2分别通过m1, mb个整数，所以m2X1 m1X2通过m〔m2个整数， 下证这m1m2个整数对模m1m2两两不同余设m2x1' m1X2' m2X1'' m1X2'' (mod m1m2),其中 x/，x ”,x2',x2''分别是 X], x2 所 通过的完全剩余系中的 数，则 m2x1' m2x1''(mod m1), m1 x2' m1x2''(mod m2), 又(m「m2) 1,故 为‘x1'' (mod m1), x2' x2'' (mod m2),这说明 m2x1 m1x2 所通过的数两两不同余，因此，m2为 m[X2也通过模m1m2的完全剩余系。
例1设m 0 (mod 2), a1, ,am及bm都是模m的完全剩余系，则 a1 b1, , am bm不是模m的完全剩余系证：因为a1, ,am及b1,,bm都是模m的完全剩余系,m所以 aii 1m(m 1) m 「 m,,、i (mod m),问理 D (mod m),2 2 i 1 2m m从而 (ai bi) aii 1 i 1mbi0 (mod m),右i a〕 b1,m,am bm是模m的完全剩余系，则 (aii 1bi) m (mod m),矛盾2因此，a1 b1,bm不是模m的完全剩余系例2证:设b c,例3则x证剩余系，故x证明：对任何正整数n,存在着仅有数字1,0组成的数a,使得n|a考察n 1个数：1,11, ,11 1,它们对模n至少有两个在同一同余 类中, n 1个1b 11 1, c 11 1, b c(modn),则 n|(b c) 11 100 0 a k个1s个1k s个1 s个0设m Z , (a,m) 1, b Z, x通过模m的一个完全剩余系，ax b1 ,八-(m1)m2从而 ■ax—b通过9J, ,Um m m max b 0 1m m m12 (m 1)。
因为x通过模m的一个完全剩余系，所 以ax b通过模m的一个完全3 简化剩余系与欧拉函数定义1欧拉函数（a）是定义在正整数集上的 函数，它的值等于序列 0,1,2, ,a 1中与a互质的数的个数注 若a是质数，则 ⑻ a 1;若a是合数，则 （a） a 1定义2 如果一个模m的剩余类中的数与 m互质，则称它为一个与 卞^m互质 的剩余类在与模m互质的全部剩余类中，从每一类各取一数所作 成的数的集合称为卞^m的一个简化剩余系定理1*Um的剩余类与模m互质的充分必要条件是 此类中有一数与m互质 因此，与模m互质的剩余类的个数为 （m）,模m的每一简化剩余系是由 与m互质 的（m）个对模m^同余的整数组成的证 设K0,K1, , Km 1是模m的全部剩余类，若Kr与模m互质，则（r,m） 1; 反之，若有krKr,（kr, m）1,则又行1 K「中任一数kr'qmkr,有（kr',m）1,即Kr与模m互质定理2 若a1,a2, ^⑺是（m）个与mill质的整数，并且两两 对模m不同余， 则a-a2, ,a皿是模m的一个简化剩余系定理3 若（a, m） 1, x通过模m的简化剩余系，则ax也通过模m的简化剩 余系。
证 axil过（m）个整数，而且由（a,m） 1, （x,m） 1可知 （ax,m） 1, 若aK axj （mod m） （i j）,则 xi xj （mod m） （i j）,与已知矛盾， 故ax通过模m的简化剩余系定理4 设rn）1, m2 Z , （m1，m2） 1,而％, x2分别通过模m1，m2的简化剩 余系，则m2x1 m1x2也通过模m1m2的简化剩余系证 由上一节定理3可知，若x1,x2分别通过模m1,m2的完全剩余系，则m2Xi miX2也通过模mim2的完全剩余系下证当Xi,X2分别通过*I^mi,m2的简 化剩余系时，m2x1 m1 x2通过模m1m2的一个完全剩余系中一 切与m1m2互质的 整数一方面，由(x1,m1)(x2,m2)(m1,m2)1 可知(m2x1,m。