初中数学竞赛讲座——数论部分7(同余).docx

第7讲 同余概念及基本性质数论有它自己代数，称为同余理论最先引进同余概念及记号是数学王子高斯先看一个游戏：有n1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜问是先走者胜还是后走者胜？应该怎样走才能取胜？取胜之道是：你只要设法使余下空格数是4倍数，以后你对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格最后只剩4个空格时，你对手就必输无疑了因此，若n除以4余数是1，2或3时，那么先走者甲胜；若n除以4余数是0话，那么后走者乙胜在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后余数是什么又例如，1999年元旦是星期五，1999年有365天，365=7×521，所以2000年元旦是星期六这里我们关心也是余数这一讲中，我们将介绍同余概念、性质及一些简单应用同余，顾名思义，就是余数相同一、基础知识定义1 给定一个正整数m，如果用m去除a，b所得余数相同，则称a及b对模m同余，记作ab(modm)，并读作a同余b，模m否则，就称a及b对于模m不同余，记作ab（mod m），根据定义，a及b是否同余，不仅及a、b有关，还及模m有关，同一对数a和b，对于模m同余，而对于模n也许就不同余，例如，58（mod 3），而58（mod 4），若a及b对模m同余，由定义1，有a=mq1r，b=mq2+r所以 a-b=m(q1-q2)，即 ma-b反之，若ma-b，设a=mq1r1，b=mq2r2，0r1，r2m-1，则有mr1-r2因r1-r2m-1，故r1-r2=0，即r1r2于是，我们得到同余另一个等价定义：定义2 若a及b是两个整数，并且它们差a-b能被一正整数m整除，那么，就称a及b对模m同余另外，根据同余定义，显然有以下几种关系是成立：aa（mod n）ab（mod m）ba（mod n）ac（mod m）ab（mod n） bc（mod m）由此可见，同余是一种等价关系，以上这三条分别叫做同余反射性，对称性和传递性，而等式也具有这几条性质二、典型例题;例1如果ab（mod m），以下命题正确有哪些？请说明理由？m | aba = b+mta = k1m+ r1，b = k2m+ r2（0r1，r2m）r1= r2解：因ab（mod m），所以可得a = k1m+ r，b = k2m+ r，那么ab=（k1k2）m，由于k1k2是整数，因此m | ab是正确根据可得ab= mt，即a= b+mt根据可得，m | r1r2，又因为0| r1r2 |m，所以| r1r2 |=0，故r1= r2例2判断正误，并说明理由如果ab（mod m）那么ka kb（mod m）如果ab（mod m），c是整数，那么a±cb±c (mod m) 如果a1b1（mod m），a2b2（mod m），那么a1±a2b1±b2 (mod m)，a1a2b1b2 (mod m)如果3a3b(mod 6 )，那么ab (mod 6 )解：ab（mod m），m | ab，m | k (ab)即m | (kakb)kakb（mod m） 成正确ab（mod m），m | ab又因为c是整数，所以m | acb+c，即m | (ac) (bc)即acbc（mod m）同理可得，a+cb+c（mod m）仿照上面两个小题方汪，可以判定这个命题也是正确显然612(mod 6)，而2 4 (mod 6)，因此，这个命题不正确说明：结论可以得到同余另一条性质，即ab（mod m）anbn（mod m）此题说明两个同余式能够象等式一样进行加、减、乘、乘方，但同余式两边却不能除以同一数，那么，同余式两边在什么情况下可以同除以一个数呢？我们先看下面例题例3由下面哪些同余式可以得到同余式ab（mod 5）3a3b（mod 5） 10a10b（mod 5）6a6b（mod 10） 10a10b（mod 20）解：因3a3b（mod 5），所以5 | 3（ab），而5 | 3 ，因此5 | ab，故ab（mod 5）由10a10b（mod 5）可以得到5 | 10（ab），而5 | 10，因此5不一定整除ab，故ab（mod 5）就成立由6a6b（mod 10）可得10 | 6（ab），而10=2×5，6=2×3，因此5 | ab，故ab（mod 5）成立由10a10b（mod 20）可得到20 | 10（ab），而20= 4×5，4 | 10，因此5 | (ab) 故ab（mod 5）不成立 综上所述，由3a3b（mod 5）或6a6b（mod 10）都可以得到ab（mod 5）说明：在中，因为（3，5）=1，因此由5 | 3（ab）一定可以得到5 | ab，进而得到ab（mod 5），一般地，如果（k，m）=1，kakb（mod m），那么ab（mod m）在中，因（6，10）=2，因此由10| 6（ab）一定可以得到5 | ab，进而得ab（mod 5），一般地，如果（k，m）= d，kakb（mod m），那么ab例4如果ab（mod 12）且ab（mod 8），那么以下同余式一定成立是哪些？ab（mod 4） ab（mod 24） ab（mod 20） ab（mod 48）解：正确有和由题中条件可得12 | ab，又因4 | 12，所以4 | ab，故ab（mod 4）因12 | ab，8| ab，所以ab是12和8公倍数，又因为8，12=24，因此ab必是24倍数，即24 | ab，故ab（mod 24）显然，当a= 26，b = 2时满足条件ab（mod 12）和ab（mod 8），但却不满足ab（mod 20）同，用a = 26，b = 2验证即可【说明】：一般地，若ab（mod m）且n | m，那么ab（mod n）若ab（mod m），ab（mod n），那么ab（mod m，n），它一个特殊情况就是：如果ab（mod m），ab（mod n）且（m，n）=1，那么ab（mod m n）【一些结论】1.同余定义等价形式ab（mod m）m | abab（mod m）a = b+mt2同余式同加、同乘性如果a1b1（mod m），a2b2（mod m）那么a1±a2b1±b2（mod m）ka1kb1（mod m）（kZ）a1a2b1b2（mod m）a1nb1n（mod m）（n是整数）3如果（k，m）=d，kakb（mod m），那么ab这条性质直接推论就是：如果（k，m）=1，kakb（mod m），那么ab（mod m）4如果ab（mod m）且n | m，那么ab（mod n）5如果ab（mod m），ab（mod n），那么ab（mod m，n）这条性质一个推论就是：如果ab（mod m），ab（mod n）且（m，n）=1，那么ab（mod m n）例5求19992002除以9余数；求1010除以7余数解：9 | 19991000，199910001（mod 9）19992000120021（mod 9），19992000除以9余数是1103（mod 7），103331（mod 7）106（1）21（mod 7），1010104（mod 7）又10292（mod 7），10210 4224（mod 7）所以1010除以7余数是4说明：求较大数余数时，可先设法找到及±1同余数，然后利用同余式性质，求出所求数余数例6求14589+32002除以13余数解：1452（mod 13），1456261（mod 13）（1456）14（1）141（mod 13）即145841（mod 13）又1455256（mod 13）所以1458914584·14556×16（mod 13）又331（mod 13），（33）667320011（mod 13），320023（mod 13）所以，14589+320026+39（mod 13）即14589+32002除以13余数是9例7求19982002十位数字分析：此题可以通过19982002末两位数来求解，及前面方法类似解：1998982（mod 100），19982002（2）20022200241001（mod 100）因为44（mod 100），4216（mod 100），4364（mod 100），4456（mod 100），4524（mod 100），4696（mod 100），4784（mod 100），4836（mod 100），4944（mod 100），41076（mod 100），4114（mod 100）所以4 n除以100余数是以4、16、64、56、24、96、84、36、44、76周期性出现，因41001=410×100+1，所以410014（mod 100），因此199820024（mod 100），故19982002十位数字是0说明：正整数幂末位数、末两位数、末三位数都具有周期性例8（1998年匈牙利奥林匹克竞赛题）求使2n+1能被3整除一切自然数n.解  则2n+1当n为奇数时，2n+1能被3整除；当n为偶数时，2n+1不能被3整除.例9 求证31980+41981能被5整除.证明  例10求20032002末位数字分析：此题就是求20032002除以10余数解：20033（mod 10），20034341（mod 10），20032002（20034）500·200331500·33277（mod 10）20022002末位数字是7说明：对于十进制整数有如下性质：例11已知n是正整数，证明48 | 72n2352n1证明：48=3×16，（3，16）=1只需证明3| 72n2352n1且16 | 72n2352n1即可71（mod 3），23520（mod 3）72n2352n112n2352×010（mod 3）3 | 72n2352n1，又2352=16×147，23520（mod 16）72n2352n149n11n10（mod 16）16 | 72n2352n1，所以48| 72n2352n1说明：当模很大时，可以用本题方法把问题化为较小模来求解，请同学位用这个方法重解例8例12已知n是任意正整数，且m | 7n+12n1，求正整数m最大值解：设an=7n+12n1，那么，a1=7+121=18，a2=72+241=72（a1，a2）=（18，72）=18，m18，下面证明对任何正整数n，都有18 | 7n+12n1又因为18=2×9，所以只须证明2 | 7n+12n，9 | 7n+12n1即可71（mod 2），7n+1211n+010（mod 2）即2 | 7n+12n1，对n进行分类讨论，若n0（mod 3），则n=3k（k为正整数）7n+12n173k+36k+1（2）3k+01（8）k11k10（mod 9）若n1（mod 3），则n=3k+1（k为非负整数）7n+12n173k+36k+127+1210（mod 9）若n2（mod 3），则n=3k+2（k为非负整数）7n+12n173k·72+36k+24172+2410（mod 9）因此，对一切自然数n，都有9 | 7n+12n1综上所述，18 | 7n+12n1，因此m最大值为18例13 把1，2，3，127，128这128个数任意排列为a1，a2，a128，计算出a1-a2，a3-a4 ，a127-a128，再将这64个数任意排列为b1，b2，b64，计算b1-b2，b3-b4，b63-b64如此继续下去，最后得到一个数x，问x是奇数还是偶数？解 因为对于一个整数a，有aa(mod 2)， a-a(mod 2)，所以b1b2b64=a1-a2+a3-a4+a127-a128a1-a2a3-a4+a127-a128a1a2a3a4+a127a128(mod 2)，因此，每经过一次“运算”，这些数和奇偶性是不改变最终得到一个数xa1a2a12812128 64×1290(mod 2)，故x是偶数例14 求证：一个十进制数被9除余数等于它各位数字之和被9除余数101(mod 9)，故对任何整数k1，有10k1k1(mod 9)因此即A被9除余数等于它各位数字之和被9除余数说明 (1)特别地，一个数能被9整除充要条件是它各位数字之和能被9整除(2)算术中“弃九验算法”就是依据本题结论10 / 10三、模拟训练1求证：(1)8(55199917)；(2) 8(32n7)；(3)17(191000-1)证 (1)因55-1(mod 8)，所以551999-1(mod 8)，55199917-117=160(mod 8)，于是8(55199917)(2)32=91(mod 8)，32n1(mod 8)，所以32n7170(mod 8)，即8(32n7)(3)192(mod 17)，19424=16-1(mod 17)，所以191000=(194)250(-1)2501(mod 17)，于是17(191000-1)2求20032002末位数字分析：此题就是求20032002除以10余数解：20033（mod 10），20034341（mod 10），20032002（20034）500·200331500·33277（mod 10）20022002末位数字是7说明：对于十进制整数有如下性质：3求2999最后两位数码.解 考虑用100除2999所得余数.又2999最后两位数字为88.4求证：22000+1不能被7整数分析：只需证明220001（mod 7）即可证明：261（mod 7），22000（26）333·221·224（mod 7），22000+15（mod 7）所以7 | 22000+15 对任意自然数n，证明A=2903n-803n-464n261n能被1897整除证 1897=7×271，7及271互质因为29035(mod 7)，8035(mod 7)，4642(mod 7)，2612(mod 7)，所以A=2903n-803n-464n+261n5n-5n-2n+2n=0(mod 7)，故7A又因为2903193(mod 271)，803261(mod 271)，464193(mod 271)，所以故271A因(7，271)=1，所以1897整除A6 任意平方数除以4余数为0和1(这是平方数重要特征)证 因为奇数2=(2k1)2=4k24k+11(mod 4)，偶数2=(2k)2=4k20(mod 4)，所以7 任意平方数除以8余数为0，1，4(这是平方数又一重要特征)证 奇数可以表示为2k1，从而奇数2=4k24k+1=4k(k1)+1因为两个连续整数k，k1中必有偶数，所以4k(k1)是8倍数，从而奇数2=8t+11(mod 8)，偶数2=(2k)2=4k2(k为整数)(1)若k=偶数=2t，则4k2=16t20(mod 8)(2)若k=奇数=2t+1，则4k2=4(2t1)2=16(t2t)+44(mod 8)，所以求余数是同余基本问题在这种问题中，先求出及±1同余数是一种基本解题技巧8 形如Fn+1，n=0，1，2，数称为费马数证明：当n2时，Fn末位数字是7证 当n2时，2n是4倍数，故令2n=4t于是Fn=22n1=24t+1=16t16t17(mod 10)，即Fn末位数字是7说明 费马数头几个是F03，F15，F217，F3257，F465537，它们都是素数费马便猜测：对所有自然数n，Fn都是素数然而，这一猜测是错误首先推翻这个猜测是欧拉，他证明了下一个费马数F5是合数