1同余的概念及基本性质

1、第三章同余 1同余的概念及其基本性质定义给定一个正整数 m，若用m去除两个整数a和b所得的余数相同，则称a,b对 模m同余，记作a b mod m .若余数不同，则称a, b对模m不同余，记作 a b mod m .甲 a a modm .(甲：jia3声调；乙：yi 3声调；丙：b)ing3声调；丁:ding1声调；戊:wu声调；己：ji3声调；庚：geng 1 -声调;辛:xin1声调天；壬：ren 2声调；癸:gui3声调.)乙若ab mod m ,则 b amodm .丙若ab modm ,b c me)dm,则acmodm.定理1 ab modmm|ab.证设 a b modm ，则

2、amqr,bmq2r,0r m. 于是a b m qq2 ,m |a b.反之，设m | a b.由带余除法,amq1r1,0r1m,bmq22,0r2m，于是，A r2 m q2 q a b .故， ml* r2，又因 r1 r2 m，故 r1 r2,a b modm .丁若 ab|modm,a2b2mod m ,则，a1a2b|b2modm .证 只证 ”的情形.因 a1 b| mod m ,a2 b2 mod m，故 m 印 b|,m a2 b2，于是 m| 印 da2b2a1a2db2，所以a1a2b|b，modm .推论若 a b c modm ,则 a c b mod m .戊若

3、a b| modm ,a2 b2 mod m ,则 a1a2 b|b2 modm .证 因 ai bi modm ,a? b? modm，故 m | 印 b, m | a? b?.又因a1a2b|b2aib|b|a2b|b2a2a1b|b|a2b2,故 m | a1a2bjb?, &尼2bb2 modm .定理A1|i|k Bq|kyi mod mXimod m ,i 1,2,|,k,特别地，若ainanXan1X1,|HAZ1 |时“ill，kB1ii| yk modm .证因Xi又因A若kam |ab,a(ii)若证 (ib modm ,i 。训小，则(I) aobnXnbn 1Xn 1

4、川y modm ,il|xkkB1|k modmb0 modm .1,2j|,k 故 Xi iyjlM k，故kXk1川丛 |xBA|kX| 1 III1, Ikkb modm , k, mka kb modm ,b mod m .yi,i 1,2,川,k，从而mod m .Xk kk% |yk1BEmod m ,1yk k mod m .1,则 a b故 m| kamod m .kb k a b .又因 k,m 1 ,故)若 a b modm ,k0,则 kakb mod km .a b mod m ,d |a,d |b, d | m,d)因 a b mod m ,k 0，故m| a b,

5、km| k a b ka kb, ka kb mod km .(ii)因 a b modm ,故 m|a b,a b mq.又因 d |a,d | b,d |m,d 0a da1, b db,m dm1, a10,b10, m10. 于是da1 db1dm1q,a1 Dmiq,aib mod mi ,adb , m mod d d辛若a b modm ,i 1,2，卅,k，则b mod mi, m?,Ill,mk因 a b modmij , i 1,2,川,k故mi |a b,i 12川，k.于是b modm,叫,|皿附记 最小公倍数的一个常用性质是，若m | a, m21 a | ,mk |

6、 a ,则mi,mbj|,mk |a.证由带余除法，设a m1,m2J|,mk q r,0 r mm,川,mk ，则 mi |a, m? |a,川，mk |a 及 g |a, m? | a,川，mk | a 得，mi | r,i 1,2,卅,k.但 耳，口2,川,叫 是0,口2,川皿 的最小公倍数，故r 0, m,m2,卅,mk |a.壬若 a b mod m , d | m,d 0,则 a b modd .证因 abmod m,故 m | a b.又因 d | m,d 0，故 d | ab, a m modd .癸若 abmodm，贝U a, m b, m .证因abmodm，故m|a b.

7、于是，存在整数 t使得ab mt.故a mtb.故a,m b, m .例一个整数a 0被9整除的充分必要条件是 n的各位数字（十进制）的和倍 9整除.证设 a an10n a. 110n 1 川 a,0 ai 10.因 10 1 mod9，故10i 1 mod9 ,a10 ai mod9 ,i 0,1,|,n于是，aai10(ii)因 1001 mod101，故 100i1 mod101 i 0 .ai mod 9 .i 0i 0n故9| a的充分必要条件是9| ai.i 0作业 P53:2,3,4,5习题选解2.设正整数a an10n 和皿1 川 a,0 a： 10,n证明11整除a的充分必

8、要条件是11整除 1冷i 0证因为101mod11，故10ii1mod11 , ai 10ii1 a mod11 ,i0,1,n.n于是，aa10ni1 ai mod11.由此可得，i 0i 0n11| a的充分必要条件是111ai.i 03.找出能被37,101整除的判别条件来解(i)因 1000 1 mod37，故 10001 mod37 i 0 .设a an1000n an11000n1 川 a,0 q 1000.则由 10001 mod37 得aJOOd ai mod37 ,i 0,1,111 ,n，故nnaai1000iai mod 37 .i 0i 0n由此可得，37 |a的充分必

9、要条件是37 ai.i 0a an100n ani100n1 川 a0,0 ai 100,则由 100i1 i mod101 得 ai 100i1 i ai mod101 ,i 0,1,川，n，故nniiaai1001 ai.i 0i 0n由此可得，101| a的充分必要条件是1011 i ai.i 024.证明 641|2n1n 12n1 而由归纳假设得a21是2n 1的倍数，又因 a为奇数，故 a21也为奇数，于是 a2 1 a2 1 1是2n 2的倍数，故 2nn 2 a 1 mod 2.1.证因28256,21665536154mod 641 ,2321542237166401 mod 641故 641|22 1.5.若a是任一奇数，则2n a1 mod2n2n1 .证对n作数学归纳法.当n 1时，因a为奇数，故可设a2a11,则a2 12耳 1 2 1 4a124a14