第 38 讲 应用同余问题一、知识要点同余这个概念最初是由伟大的德国数学家高斯发现的。同余的定义是这样的：两个整数 a，b，如果它们除以同一自然数 m 所得的余数想同，则称 a，b 对于模 m 同余。记作：a≡b（mod　ｍ）。读做：ａ同余于ｂ模ｍ。比如，12 除以 5，47 除以 5，它们有相同的余数 2，这时我们就说，对于除数 5，12 和 47 同余，记做 12≡47（mod　5）。同余的性质比较多，主要有以下一些：性质（1）：对于同一个除数，两个数之和（或差）与它们的余数之和（或差）同余。比如：32 除以 5 余数是 2，19 除以 5 余数是 4，两个余数的和是 2+4=6。“32+19”除以 5 的余数就恰好等于它们的余数和 6 除以 5 的余数。也就是说，对于除数 5，“32+19”与它们的余数和“2+4”同余，用符号表示就是：32≡2（mod　5），19≡4（mod　5），32+19≡2+4≡1（mod　5）性质（2）：对于同一个除数，两个数的乘积与它们余数的乘积同余。性质（3）：对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。性质（4）：对于同一个除数，如果两个整数同余，那么它们的乘方仍然同余。应用同余性质几萼体的关键是要在正确理解的基础上灵活运用同余性质。把求一个较大的数除以某数的余数问题转化为求一个较小的数除以这个数的余数，使复杂的题变简单，使困难的题变容易。二、精讲精练【例题 1】求 1992×59 除以 7 的余数。应用同余性质（2）可将 1992×59 转化为求 1992 除以 7 和 59 除以 7 的余数的乘积，使计算简化。1992 除以 7 余 4，59 除以 7 余 3。根据同余性质，“4×3”除以 7 的余数与“1992×59”除以 7 的余数应该是相同的，通过求“4×3”除以 7 的余数就可知道 1992×59 除以 7 的余数了。因为 1992×59≡4×3≡5（mod 7）所以 1992×59 除以 7 的余数是 5。练习 1：1、求 4217×364 除以 6 的余数。2、求 1339655×12 除以 13 的余数。3、求 879×4376×5283 除以 11 的余数。【例题 2】已知 2001 年的国庆节是星期一，求 2010 年的国庆节是星期几？一星期有 7 天，要求 2010 年的国庆节是星期几，就要求从 2001 年到 2010 年的国庆节的总天数被 7除的余数就行了。但在甲酸中，如果我们能充分利用同余性质，就可以不必算出这个总天数。2001 年国庆节到 2010 年国庆节之间共有 2 个闰年 7 个平年，即有“366×2+365×7”天。因为366×2≡2×2≡4（mod 7），365×7≡1×7≡0（mod 7），366×2+365×7≡2×2+1×7≡4+0≡4（mod7）答：2010 年的国庆节是星期五。练习 2：1、已知 2002 年元旦是星期二。求 2008 年元旦是星期几？2、已知 2002 年的“七月一日”是星期一。求 2015 年的“十月一日”是星期几？3、今天是星期四，再过 365 的 15 次方是星期几？【例题 3】求 2001 的 2003 次方除以 13 的余数。2001 除以 13 余 12，即 2001≡12（mod 13）。根据同余性质（4），可知 2001 的 2003 次方≡12 的2003 次方（mod 13），但 12 的 2003 次方仍然是一个很大的值，要求它的余数比较困难。这时的关键就是要找出 12 的几次方对模 13 与 1 是同余的。经试验可知 12 的平方≡1（mod 13），而2003≡2×1001+1。所以（12 的平方）的 1001 次方≡1 的 1001（mod 13），即 12 的 2002 次方≡1（mod13），而 12 的 2003 次方≡12 的 2002 次方×12。根据同余性质（2）可知 12 的 2002 次方×12≡1×12≡12（mod 13）因为：2001 的 2003 次方≡12 的 2003 次方（mod 13）12 的平方≡1（mod 13），而 2003≡2×1001+112 的 2003 次方≡12 的 2002 次方×12≡1×12≡12（mod 13） 所以 2001 的 2003 次方除以 13 的余数是 12。练习 3：1、求 12 的 200 次方除以 13 的余数。2、求 3 的 92 次方除以 21 余几。3、9 个小朋友坐成一圈，要把 35 的 7 次方粒瓜子平均分给他们，最后剩下几粒？【例题 4】自然数 16520，14903，14177 除以 m 的余数相同，m 最大是多少？自然数 16520，14903，14177 除以 m 的余数相同，换句话说就是 16520≡14903≡14177（mod m）。根据同余性质（3），这三个饿数同余，那么它们的差就能被 m 整除。要求 m 最大是多少，就是求它们差的最大公约数是多少？因为 16520—14903=1617=3×7 的平方×1116520—14177=2343=3×11×71 14903—14177=726=2×3×11 的平方M 是这些差的公约数，m 最大是 3×11=33。练习 4：1、若 2836、4582、5164、6522 四个整数都被同一个两位数相除，所得的余数相同。除数是多少？2、一个整数除 226、192、141 都得到相同的余数，且余数不为 0，这个整数是几？3、当 1991 和 1769 除以某一个自然数 m 时，余数分别为 2 和 1，那么 m 最小是多少？【例题 5】某数用 6 除余 3，用 7 除余 5，用 8 除余 1，这个数最小是几？我们可从较大的除数开始尝试。首先考虑与 1 模 8 同余的数，9≡1（mod 8），但 9 输以 7 余数不是 5，所以某数不是 9。17≡1（mod 8），17 除以 7 的余数也不是 5。25≡1（mod 8），25 除以 7 的余数也不是 5。33≡1（mod 8），33 除以 7 的余数正好是 5，而且 33 除以 6 余数正好是 3，所以这个数最小是 33。上面的方法实际是一种列举法，也可以简化为下面的格式：被 8 除余 1 的数有：9，17，25，33，41，49，57，65，73，81，89，……其中被 7 除余 5 的数有：33，89，……这些数中被 6 除余 3 的数最小是 33。练习 5：1、某数除以 7 余 1，除以 5 余 1，除以 12 余 9。这个数最小是几？2、某数除以 7 余 6，除以 5 余 1，除以 11 余 3，求此数最小值。3、在一个圆圈上有几十个孔（如图 38-1），小明像玩跳棋那样从 A 孔出发沿逆时针方向每隔几个孔跳一步，希望一圈以后能跑回 A 孔，他先试着每隔 2 孔跳一步，也只能跳到 B 孔。最后他每隔 6 孔跳一步，正好跳回 A 孔。问：这个圆圈上共有多少个孔？