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

鼎吉教育遵循：“授人以鱼，不如授人以渔”的教育理念秉承：以人为本，质量第一，突出特色，服务家长初中数学兴趣班系列讲座——数论部分唐一良数学工作室◆以鲜明的教育理念启发人◆以浓厚的学习氛围影响人第页◆以不倦的育人精神感染人◆以优良的学风学纪严律人◆第页共NUMPAGES10页第7讲同余的概念及基本性质数论有它自己的代数，称为同余理论．最先引进同余的概念与记号的是数学王子高斯．先看一个游戏：有n＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移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×52＋1，所以2000年的元旦是星期六．这里我们关心的也是余数．这一讲中，我们将介绍同余的概念、性质及一些简单的应用．同余，顾名思义，就是余数相同．一、基础知识定义1给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作a≡b(modm)，并读作a同余b，模m．否则，就称a与b对于模m不同余，记作a≡b（modm），根据定义，a与b是否同余，不仅与a、b有关，还与模m有关，同一对数a和b，对于模m同余，而对于模n也许就不同余，例如，5≡8（mod3），而5≡8（mod4），若a与b对模m同余，由定义1，有a=mq1＋r，b=mq2+r．所以a-b=m(q1-q2)，即m｜a-b．反之，若m｜a-b，设a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2．于是，我们得到同余的另一个等价定义：定义2若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a与b对模m同余．另外，根据同余的定义，显然有以下几种关系是成立的：⑴a≡a（modn）⑵a≡b（modm）b≡a（modn）a≡c（modm）⑶a≡b（modn）b≡c（modm）由此可见，同余是一种等价关系，以上这三条分别叫做同余的反射性，对称性和传递性，而等式也具有这几条性质．二、典型例题;例1．如果a≡b（modm），以下命题正确的有哪些？请说明理由？⑴m|a－b⑵a=b+mt⑶a=k1m+r1，b=k2m+r2（0≤r1，r2＜m）r1=r2解：⑴因a≡b（modm），所以可得a=k1m+r，b=k2m+r，那么a－b=（k1－k2）m，由于k1－k2是整数，因此m|a－b是正确的．⑵根据⑴可得a－b=mt，即a=b+mt⑶根据⑴可得，m|r1－r2，又因为0≤|r1－r2|＜m，所以|r1－r2|=0，故r1=r2．例2．判断正误，并说明理由．⑴如果a≡b（modm）那么ka≡kb（modm）⑵如果a≡b（modm），c是整数，那么a±c≡b±c(modm)⑶如果a1≡b1（modm），a2≡b2（modm），那么a1±a2≡b1±b2(modm)，a1a2≡b1b2(modm)．⑷如果3a≡3b(mod6)，那么a≡b(mod6)解：⑴∵a≡b（modm），∴m|a－b，∴m|k(a－b)即m|(ka－kb)∴ka≡kb（modm）⑴成正确⑵∵a≡b（modm），∴m|a－b又因为c是整数，所以m|a－c－b+c，即m|(a－c)－(b－c)即a－c≡b－c（modm）同理可得，a+c≡b+c（modm）⑶仿照上面的两个小题的方汪，可以判定这个命题也是正确的⑷显然6≡12(mod6)，而2≡4(mod6)，因此，这个命题不正确说明：⑶的结论可以得到同余的另一条性质，即a≡b（modm）an≡bn（modm）此题说明两个同余式能够象等式一样进行加、减、乘、乘方，但同余式两边却不能除以同一数，那么，同余式的两边在什么情况下可以同除以一个数呢？我们先看下面的例题．例3．由下面的哪些同余式可以得到同余式a≡b（mod5）①3a≡3b（mod5）②10a≡10b（mod5）③6a≡6b（mod10）④10a≡10b（mod20）解：①因3a≡3b（mod5），所以5|3（a－b），而5|3，因此5|a－b，故a≡b（mod5）②由10a≡10b（mod5）可以得到5|10（a－b），而5|10，因此5不一定整除a－b，故a≡b（mod5）就成立③由6a≡6b（m