全国初中数学竞赛辅导(八年级)教学案全集第25讲 同余式

全国初中数学竞赛辅导八年级教学案全集第二十五讲同余式数论有它自己的代数，称为同余理论最先引进同余的概念与记号的是数学王子高斯先看一个游戏有N1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜问是先走者胜还是后走者胜应该怎样走才能取胜取胜之道是你只要设法使余下的空格数是4的倍数，以后你的对手若走I格I1，2，3，你走4I格，即每一次交替，共走了4格最后只剩4个空格时，你的对手就必输无疑了因此，若N除以4的余数是1，2或3时，那么先走者甲胜；若N除以4的余数是0的话，那么后走者乙胜在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用M除后的余数是什么又例如，1999年元旦是星期五，1999年有365天，3657521，所以2000年的元旦是星期六这里我们关心的也是余数这一讲中，我们将介绍同余的概念、性质及一些简单的应用同余，顾名思义，就是余数相同定义1给定一个正整数M，如果用M去除A，B所得的余数相同，则称A与B对模M同余，记作ABMODM，并读作A同余B，模M若A与B对模M同余，由定义1，有AMQ1R，BMQ2R所以ABMQ1Q2，即MAB反之，若MAB，设AMQ1R1，BMQ2R2，0R1，R2M1，则有MR1R2因R1R2M1，故R1R20，即R1R2于是，我们得到同余的另一个等价定义定义2若A与B是两个整数，并且它们的差AB能被一正整数M整除，那么，就称A与B对模M同余同余式的写法，使我们联想起等式其实同余式和代数等式有一些相同的性质，最简单的就是下面的定理1定理11AAMODM2若ABMODM，则BAMODM3若ABMODM，BCMODM，则ACMODM在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立定理2若ABMODM，CDMODM，则ACBDMODM，ACBDMODM证由假设得MAB，MCD，所以MACBD，MCABBCD，即ACBDMODM，ACBDMODM由此我们还可以得到若ABMODM，K是整数，N是自然数，则AKBKMODM，AKBKMODM，ANBNMODM对于同余式ACBCMODM，我们是否能约去公约数C，得到一个正确的同余式ABMODM在这个问题上，同余式与等式是不同的例如255MOD10，约去5得51MOD10这显然是不正确的但下面这种情形，相约是可以的定理3若ACBCMODM，且C，M1，则ABMODM证由题设知ACBCABCMK由于M，C1，故MAB，即ABMODM定理4若N2，ABMODM1，ABMODM2，ABMODMN，且MM1，M2，MN表示M1，M2，MN的最小公倍数，则ABMODM前面介绍了同余式的一些基本内容，下面运用同余这一工具去解决一些具体问题应用同余式的性质可以简捷地处理一些整除问题若要证明M整除A，只需证A0MODM即可例1求证1855199917；2832N7；3171910001证1因551MOD8，所以5519991MOD8，55199917117160MOD8，于是85519991723291MOD8，32N1MOD8，所以32N7170MOD8，即832N73192MOD17，19424161MOD17，所以19100019425012501MOD17，于是171910001例2求使2N1为7的倍数的所有正整数N解因为2381MOD7，所以对N按模3进行分类讨论1若N3K，则2N123K18K11K10MOD7；2若N3K1，则2N1223K128K121K11MOD7；3若N3K2，则2N12223K148K141K13MOD7所以，当且仅当3N时，2N1为7的倍数例3对任意的自然数N，证明A2903N803N464N261N能被1897整除证18977271，7与271互质因为29035MOD7，8035MOD7，4642MOD7，2612MOD7，所以A2903N803N464N261N5N5N2N2N0MOD7，故7A又因为2903193MOD271，803261MOD271，464193MOD271，所以故271A因7，2711，所以1897整除A例4把1，2，3，127，128这128个数任意排列为A1，A2，A128，计算出A1A2，A3A4，A127A128，再将这64个数任意排列为B1，B2，B64，计算B1B2，B3B4，B63B64如此继续下去，最后得到一个数X，问X是奇数还是偶数解因为对于一个整数A，有AAMOD2，AAMOD2，所以B1B2B64A1A2A3A4A127A128A1A2A3A4A127A128A1A2A3A4A127A128MOD2，因此，每经过一次“运算”，这些数的和的奇偶性是不改变的最终得到的一个数XA1A2A12812128641290MOD2，故X是偶数如果要求一个整数除以某个正整数的余数，同余是一个有力的工具另外，求一个数的末位数字就是求这个数除以10的余数，求一个数的末两位数字就是求这个数除以100的余数例5求证一个十进制数被9除的余数等于它的各位数字之和被9除的余数101MOD9，故对任何整数K1，有10K1K1MOD9因此即A被9除的余数等于它的各位数字之和被9除的余数说明1特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除2算术中的“弃九验算法”就是依据本题的结论例6任意平方数除以4余数为0和1这是平方数的重要特征证因为奇数22K124K24K11MOD4，偶数22K24K20MOD4，所以例7任意平方数除以8余数为0，1，4这是平方数的又一重要特征证奇数可以表示为2K1，从而奇数24K24K14KK11因为两个连续整数K，K1中必有偶数，所以4KK1是8的倍数，从而奇数28T11MOD8，偶数22K24K2K为整数1若K偶数2T，则4K216T20MOD82若K奇数2T1，则4K242T1216T2T44MOD8，所以求余数是同余的基本问题在这种问题中，先求出与1同余的数是一种基本的解题技巧例81求33除21998的余数2求8除72N11的余数解1先找与1MOD33同余的数因为25321MOD33，所以2101MOD33，219982101992523825MOD33，所求余数为252因为71MOD8，所以72N112N11MOD8，72N1126MOD8，即余数为6例9形如FN22N1，N0，1，2，的数称为费马数证明当N2时，FN的末位数字是7证当N2时，2N是4的倍数，故令2N4T于是FN22N124T116T16T17MOD10，即FN的末位数字是7说明费马数的头几个是F03，F15，F217，F3257，F465537，它们都是素数费马便猜测对所有的自然数N，FN都是素数然而，这一猜测是错误的首先推翻这个猜测的是欧拉，他证明了下一个费马数F5是合数证明F5是合数，留作练习利用同余还可以处理一些不定方程问题例10证明方程X4Y425Z没有整数解证对于任一整数X，以5为模，有X0，1，2MOD5，X20，1，4MOD5，X40，1，1MOD5，即对任一整数X，X40，1MOD5同样，对于任一整数YY40，1MOD5，所以X4Y422，3，4MOD5，从而所给方程无整数解说明同余是处理不定方程的基本方法，但这种方法也非常灵活，关键在于确定所取的模本例我们