《初中数学竞赛讲座数论部分7同余》由会员分享，可在线阅读，更多相关《初中数学竞赛讲座数论部分7同余（10页珍藏版）》请在金锄头文库上搜索。
1、初中数学竞赛讲座数论部分7(同余)第7讲 同余的概念及基本性质数论有它自己的代数，称为同余理论最先引进同余的概念与记号的是数学王子高斯先看一个游戏：有n1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜问是先走者胜还是后走者胜？应该怎样走才能取胜？取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格最后只剩4个空格时，你的对手就必输无疑了因此，若n除以4的余数是1，2或3时，那么先走者甲胜；若n除以4的余数是0的话，那么后走者乙胜在这个游戏里，我们可以看出，有时我们
2、不必去关心一个数是多少，而要关心这个数用m除后的余数是什么又例如，1999年元旦是星期五，1999年有365天，365=7521，所以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（m
3、od 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）由此可见，同余是一种等价关系，以上这三条分别叫做同余的反射性
4、，对称性和传递性，而等式也具有这几条性质二、典型例题;例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），
5、c是整数，那么acbc (mod m) 如果a1b1（mod m），a2b2（mod m），那么a1a2b1b2 (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)，因此，这
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不一定整除
7、ab，故ab（mod 5）就成立由6a6b（mod 10）可得10 | 6（ab），而10=25，6=23，因此5 | ab，故ab（mod 5）成立由10a10b（mod 20）可得到20 | 10（ab），而20= 45，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|
8、 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）和
9、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）那么a1a2b1b2（mod m）ka1kb1（mod m）（kZ）a1a2b1b2（mo
10、d 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），19
11、992000除以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）所以14589145841455616（mod 13）又331（mod 13）
12、，（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），4
13、944（mod 100），41076（mod 100），4114（mod 100）所以4 n除以100的余数是以4、16、64、56、24、96、84、36、44、76周期性出现的，因41001=410100+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求20
14、032002的末位数字分析：此题就是求20032002除以10的余数解：20033（mod 10），20034341（mod 10），20032002（20034）50020033150033277（mod 10）20022002的末位数字是7说明：对于十进制的整数有如下性质：例11已知n是正整数，证明48 | 72n2352n1证明：48=316，（3，16）=1只需证明3| 72n2352n1且16 | 72n2352n1即可71（mod 3），23520（mod 3）72n2352n112n2352010（mod 3）3 | 72n2352n1，又2352=16147，23520（mod 16）72n2352n149n11n10（mod 16）
