第三章 同余§1 同余的概念及其基本性质定义 给定一个正整数m ，若用m 去除两个整数a 和b 所得的余数相同，则称,a b 对模m 同余，记作()mod .a b m ≡若余数不同，则称,a b 对模m 不同余，记作()\mod a b m ≡.甲 ()mod .a a m ≡（甲：jia 3声调； 乙：yi 3声调； 丙：bing 3声调； 丁：ding 1声调； 戊：wu 声调； 己：ji 3声调； 庚：geng 1声调； 辛: xin 1声调 天； 壬: ren 2声调； 癸: gui 3声调.）乙 若()mod ,a b m ≡则()mod .b a m ≡丙 若()()mod ,mod ,a b m b c m ≡≡则()mod .a c m ≡ 定理1 ()mod |.a b m m a b ≡⇔-证 设()mod a b m ≡，则12,,0.a mq r b mq r r m =+=+≤<于是，()12,|.a b m q q m a b -=--反之，设|.m a b -由带余除法，111222,0,,0a mq r r m b mq r r m =+≤<=+≤<，于是，()()1221.r r m q q a b -=-+-故，12|m r r -，又因12r r m -<，故()12,mod .r r a b m =≡丁 若()()1122mod ,mod ,a b m a b m ≡≡则，()1212mod .a a b b m ±≡±证 只证“+”的情形.因()()1122mod ,mod a b m a b m ≡≡，故1122,m a b m a b --，于是()()()()11221212|m a b a b a a b b -+-=+-+，所以()1212mod .a a b b m +≡+ 推论 若()mod ,a b c m +≡则()mod .a c b m ≡-戊 若()()1122mod ,mod ,a b m a b m ≡≡则()1212mod .a a bb m ≡ 证 因()()1122mod ,mod a b m a b m ≡≡，故1122|,|.m a b m a b --又因()()()1212111212211122,a a bb a b b a bb a a b b a b -=-+-=-+-故()12121212|,mod .m a a bb a a bb m -≡ 定理2 若()()11mod ,mod ,1,2,,,kki i A B m x y m i k αααα≡≡=则()11111111,,,,mod .k k k kkkk k A xx B y y m αααααααααααα≡∑∑特别地，若()mod ,0,1,,i i a b m i n ≡=，则()111010mod .n n n n n n n n a x a x a b x b x b m ----+++≡+++证 因()mod ,1,2,,i i x y m i k ≡=故,1,2,,iii i x y i k αα≡=，从而()1111mod .k k k k x x y y m αααα≡又因()11mod kkA B m αααα≡，故()()111111111111111,,,,mod ,mod .k k kk k k kkkk k k k A xx B y y m A xx B y y m αααααααααααααααααααα≡≡∑∑己 若()()mod ,,1,ka kb m k m ≡=则()mod .a b m ≡证 因()mod ka kb m =，故()|.m ka kb k a b -=-又因(),1k m =，故()|,mod .m a b a b m -≡庚 （ⅰ）若()mod ,0,a b m k ≡>则()mod .ka kb km ≡ （ⅱ）若()mod ,|,|,|,0,a b m d a d b d m d ≡>则mod .a b m d d d ⎛⎫≡ ⎪⎝⎭证 （ⅰ）因()mod ,0a b m k ≡>，故()()|,|,mod .m a b km k a b ka kb ka kb km --=-≡（ⅱ）因()mod ,a b m ≡故|,.m a b a b mq --=又因|,|,|,0d a d b d m d >111111,,,0,0,0a da b db m dm a b m ===>>>. 于是()111111111,,mod ,mod .a b m da db dm q a b m q a b m d d d ⎛⎫-=-=≡≡ ⎪⎝⎭辛 若()mod ,1,2,,i a b m i k ≡=，则[]()12mod ,,,.k a b m m m ≡证 因()mod ,1,2,,i a b m i k ≡=，故|,1,2,,.i m a b i k -=于是，[][]()1212,,,|,mod ,,,.k k m m m a b a b m m m -≡附记 最小公倍数的一个常用性质是，若12|,|,,|k m a m a m a ，则[]12,,,|.k m m m a证 由带余除法，设[][]1212,,,,0,,,k k a m m m q r r m m m =+≤<，则12|,|,,|k m a m a m a 及12|,|,,|k m a m a m a 得， |,1,2,,.i m r i k =但[]12,,,k m m m 是12,,,k m m m 的最小公倍数，故[]120,,,,|.k r m m m a =壬 若()mod ,|,0,a b m d m d ≡>则()mod .a b d ≡证 因()mod ,a b m ≡故|.m a b -又因|,0d m d >，故()|,mod .d a b a m d -≡ 癸 若()mod a b m ≡，则()(),,.a m b m =证 因()mod a b m ≡，故|.m a b -于是，存在整数t 使得.a b mt -=故.a mt b =+故()(),,.a m b m =例 一个整数0a >被9整除的充分必要条件是n 的各位数字（十进制）的和倍9整除.证 设1101010,010n n n n i a a a a a --=+++≤<.因()101mod9≡，故()()101mod9,10mod9,0,1,,.i i i i a a i n ≡≡=于是，()010mod 9.n nii i i i a a a ===≡∑∑故9|a 的充分必要条件是09|.ni i a =∑作业 P53:2,3,4,5.习题选解2.设正整数1101010,010,n n n n i a a a a a --=+++≤<证明11整除a 的充分必要条件是11整除()01.niii a =-∑证 因为()101mod11≡-，故()()()()101mod11,101mod11,0,1,,.i ii i i i a a i n ≡-≡-=.于是，()()0101mod11.n nii iii i a a a ===≡-∑∑由此可得，11|a 的充分必要条件是()0111.nii i a =-∑3.找出能被37,101整除的判别条件来.解 （ⅰ）因()10001mod37≡，故()()10001mod370.ii ≡≥设11010001000,01000.n n n n i a a a a a --=+++≤<则由()10001mod37i≡得()1000mod37,0,1,,ii i a a i n ≡=，故()01000mod 37.n nii i i i a a a ===≡∑∑由此可得，37|a 的充分必要条件是037.ni i a =∑（ⅱ）因()1001mod101≡-，故()()()1001mod1010.iii ≡-≥ 设110100100,0100,n n n n i a a a a a --=+++≤<则由()()1001mod101ii ≡-得()()1001mod101,0,1,,ii i i a a i n ≡-=，故()01001.n niii i i i a a a ===≡-∑∑由此可得，101|a 的充分必要条件是()01011.niii a =-∑4.证明52641|2 1.+ 证 因()()8163222256,265536154mod 641,2154237166401mod 641,==≡≡=≡≡-故52641|2 1.+5.若a 是任一奇数，则()()221mod 21.nn a n +≡≥证 对n 作数学归纳法.当1n =时，因a 为奇数，故可设121a a =+，则()()2221111112114441a a a a a a -=+-=+=+.而()111a a +是两个连续两个整数的积，一定是2的倍数，从而()122128|1,1mod 2,a a +-≡即1n =时结论正确.假设对()12n n -≥结论正确，即()12121mod 2.n n -+≡下面说明在此假设下，对n 结论正确.因()()()111222221111nn n n a aa a ----=-=-+，而由归纳假设得121n a--是12n +的倍数，又因a 为奇数，故121n a -+也为奇数，于是()()112211n n a a ---+是22n +的倍数，故()221mod 2.nn a +≡。