2019-2020年初中数学竞赛辅导 第四十六讲《同余式》教案1 北师大版.doc

2019-2020年初中数学竞赛辅导 第四十六讲同余式教案1 北师大版数论有它自己的代数，称为同余理论最先引进同余的概念与记号的是数学王子高斯先看一个游戏：有n1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜问是先走者胜还是后走者胜？应该怎样走才能取胜？取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格最后只剩4个空格时，你的对手就必输无疑了因此，若n除以4的余数是1，2或3时，那么先走者甲胜；若n除以4的余数是0的话，那么后走者乙胜在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么又例如，xx年元旦是星期五，xx年有365天，365=7521，所以xx年的元旦是星期六这里我们关心的也是余数这一讲中，我们将介绍同余的概念、性质及一些简单的应用同余，顾名思义，就是余数相同定义1 给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作ab(modm)，并读作a同余b，模m若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同余同余式的写法，使我们联想起等式其实同余式和代数等式有一些相同的性质，最简单的就是下面的定理1定理1 (1)aa(modm)(2) 若ab(modm)，则ba(modm)(3) 若ab(modm)，bc(modm)，则ac(modm)在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立定理2 若ab(modm)，cd(modm)，则acbd(modm)，acbd(modm)证 由假设得ma-b，mc-d，所以m(ac)-(bd)， mc(a-b)b(c-d)，即acbd(modm)，acbd(modm)由此我们还可以得到：若ab(modm)，k是整数，n是自然数，则akbk(modm)，akbk(modm)，anbn(modm)对于同余式acbc(modm)，我们是否能约去公约数c，得到一个正确的同余式ab(modm)？在这个问题上，同余式与等式是不同的例如255(mod 10)，约去5得51(mod 10)这显然是不正确的但下面这种情形，相约是可以的定理3 若acbc(modm)，且(c，m)=1，则ab(modm)证 由题设知ac-bc=(a-b)c=mk由于(m，c)=1，故ma-b，即ab(modm)定理4 若n2，ab(modm1)，ab(modm2)，ab(modmn)，且M=m1，m2，mn表示m1，m2，mn的最小公倍数，则ab(modM)前面介绍了同余式的一些基本内容，下面运用同余这一工具去解决一些具体问题应用同余式的性质可以简捷地处理一些整除问题若要证明m整除a，只需证a0(modm)即可例1 求证：(1)8(55xx17)；(2) 8(32n7)；(3)17(191000-1)证 (1)因55-1(mod 8)，所以55xx-1(mod 8)，55xx17-117=160(mod 8)，于是8(55xx17)(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 求使2n-1为7的倍数的所有正整数n解 因为2381(mod 7)，所以对n按模3进行分类讨论(1) 若n=3k，则2n-1(23)k-18k-11k-10(mod 7)；(2) 若n=3k1，则2n-1=2(23)k-1=28k-121k-11(mod 7)；(3) 若n=3k2，则2n-1=22(23)k-1=48k-141k-13(mod 7)所以，当且仅当3n时，2n-1为7的倍数例3 对任意的自然数n，证明A=2903n-803n-464n261n能被1897整除证 1897=7271，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整除A例4 把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 641290(mod 2)，故x是偶数如果要求一个整数除以某个正整数的余数，同余是一个有力的工具另外，求一个数的末位数字就是求这个数除以10的余数，求一个数的末两位数字就是求这个数除以100的余数例5 求证：一个十进制数被9除的余数等于它的各位数字之和被9除的余数101(mod 9)，故对任何整数k1，有10k1k1(mod 9)因此即A被9除的余数等于它的各位数字之和被9除的余数说明 (1)特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除(2)算术中的“弃九验算法”就是依据本题的结论例6 任意平方数除以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 (1)求33除2xx的余数(2)求8除72n+1-1的余数解 (1)先找与1(mod 33)同余的数因为2532-1(mod 33)，所以 2101(mod 33)，2xx=(210)1992523-825(mod 33)，所求余数为25(2)因为7-1(mod 8)，所以72n1(-1)2n1-1(mod 8)，72n1-1-26(mod 8)，即余数为6例9 形如Fn22n+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是合数证明F5是合数，留作练习利用同余还可以处理一些不定方程问题例10 证明方程x4+y4+2=5z没有整数解证 对于任一整数x，以5为模，有x0，1，2(mod 5)，x20，1，4(mod 5)，x40，1，1(mod 5)，即对任一整数x，x40，1(mod 5)同样，对于任一整数yy40，1(mod 5)，所以 x4+y4+22，3，4(mod 5)，从而所给方程无整数解说明 同余是处理不定方程的基本方法，但这种方法也非常灵活，关键在于确定所取的模(本例我们取模5)，这往往应根据问题的特点来确定练习二十五1求证：17(191000-1)2证明：对所有自然数n，330(62n-52n-11)4求21000除以13的余数5求1525359951005除以4所得的余数6今天是星期天，过3100天是星期几？再过5xx天又是星期几？7求n=1357xx的末三位数字8证明不定方程x2+y2-8z=6无整数解