《八年级数学竞赛 第25讲 同余式.docx》由会员分享，可在线阅读，更多相关《八年级数学竞赛 第25讲 同余式.docx（15页珍藏版）》请在三一文库上搜索。
1、八年级数学竞赛 第二十五讲 同余式数论有它自己的代数，称为同余理论最先引进同余的概念与记号的 是数学王子高斯先看一个游戏：有 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=7×521，所以 2000 年的元旦是星期六这里我 们关心的也是余数这一讲中，我们将介绍同余的概念、性质及一些简单 的应用同余，顾名思义，就是余数相同定义 1 给定一个正整数 m，如果用 m 去除 a，b 所得的余数相同，则 称 a 与 b 对模 m 同余，记作ab(modm)，并读作 a 同余 b，模 m若 a 与 b 对模 m 同余，由定义 1，有a=mq r，b=mq +r12所以 a-b=m(q
3、-q )，1 2即 ma-b反之，若 ma-b，设a=mq r ，b=mq r ，0r ，r m-1，1 1 2 2 1 2则有 mr -r 因r -r m-1，故 r -r =0，即 r r 1 2 1 2 1 2 1 2于是，我们得到同余的另一个等价定义：定义 2 若 a 与 b 是两个整数，并且它们的差 a-b 能被一正整数 m 整除， 那么，就称 a 与 b 对模 m 同余同余式的写法，使我们联想起等式其实同余式和代数等式有一些相 同的性质，最简单的就是下面的定理 1定理 1 (1)aa(modm)(2) 若 ab(modm)，则 ba(modm)(3) 若 ab(modm)，bc(m
4、odm)，则 ac(modm)在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立 定理 2 若 ab(modm)，cd(modm)，则a±cb±d(modm)，acbd(modm)证 由假设得 ma-b，mc-d，所以m(a±c)-(b±d)， mc(a-b)b(c-d)，即a±cb±d(modm)，acbd(modm)由此我们还可以得到：若 ab(modm)，k 是整数，n 是自然数，则a±kb±k(modm)，akbk(modm)，anbn(modm)对于同余式 acbc(modm)，我们是否能约去公
5、约数 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(modm )，1ab(modm )，2ab(modm )，n且 M=m ，m ，m 表示 m ，m ，m 的最小公倍数，则12n12nab(modM)前面介绍了同余式的一些基本内容，下面运用同余这一工具去解决一 些具
6、体问题应用同余式的性质可以简捷地处理一些整除问题若要证明 m 整除 a， 只需证 a0(modm)即可例 1 求证：(1)8(55199917)；(2) 8(32n7)；(3)17(191000-1)证 (1)因 55-1(mod 8)，所以 551999-1(mod 8)，55199917-117=16 0(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
7、)，于是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，则(3) 若 n=3k2，则2n-1=2·(23)k-1=2·8k-1 2·1k-11(mod 7)；2n-1=22·(23)k-1=4·8k-14·1k-13(mod 7)所以，当且仅当 3n 时，2n-1 为 7 的倍数例 3 对任意的自然数 n，证明A=2903n-803n-
8、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 整除 A例 4 把 1，2，3，127，128 这 128 个数任意排列为 a ，a ，a ，计算出a -a ，a -a ，a -a ， 1 2 3
9、4 127 128再将这 64 个数任意排列为 b ，b ，b ，计算1 21281264b -b ，b -b ，b -b 1 2 3 4 63 64如此继续下去，最后得到一个数 x，问 x 是奇数还是偶数？ 解 因为对于一个整数 a，有aa(mod 2)， a-a(mod 2)，所以b b b1264=a -a +a -a +a -a 1 2 3 4 127 128a -a a -a +a -a1 2 3 4 127128a a a a +a a (mod 2)，1234127128因此，每经过一次“运算”，这些数的和的奇偶性是不改变的最终 得到的一个数xa a a 121281212864
10、×1290(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
11、 和 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
12、8)，所以求余数是同余的基本问题在这种问题中，先求出与±1 同余的数是 一种基本的解题技巧例 8 (1)求 33 除 21998 的余数(2)求 8 除 72n+1-1 的余数解 (1)先找与±1(mod 33)同余的数因为2532-1(mod 33)，所以 2101(mod 33)，21998=(210)199·25·23-825(mod 33)，所求余数为 25(2)因为 7-1(mod 8)，所以72n1(-1)2n1-1(mod 8)，即余数为 6例 9 形如72n1-1-26(mod 8)，F 22n+1，n=0，1，2，n的数称为费马数证明：
13、当 n2 时，F 的末位数字是 7n证 当 n2 时，2n是 4 的倍数，故令 2n=4t于是F =22n1=24t+1=16t1n6t17(mod 10)，即 F 的末位数字是 7n说明 费马数的头几个是F 3，F 5，F 17，F 257，F 65537，01234它们都是素数费马便猜测：对所有的自然数 n，F 都是素数然而，n这一猜测是错误的首先推翻这个猜测的是欧拉，他证明了下一个费马数 F 是合数证明 F 是合数，留作练习55利用同余还可以处理一些不定方程问题 例 10 证明方程x4+y4+2=5z没有整数解证 对于任一整数 x，以 5 为模，有x0，±1，±2(m
14、od 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天是星期几？再过 51998天又是星期几？7求 n=1×3×5×7××1999 的末三位数字8证明不定方程 x2+y2-8z=6 无整数解