1、第十八讲 同余问题第一部分：趣味数学韩信巧点兵大将军韩信去校场清点兵马。1000名左右的士兵整整齐齐地排列在操场上。韩信身披战袍,威风凛凛地挥动令旗,开始指挥军队。韩信把手中的令旗向左一挥,士兵们的队形立刻开始变化,排成了3列纵队,韩信看到,最后一排不足3人,只有2人。接着,令旗向右一挥,队形又变化了,这回变成了5列纵队,仍然还有一排人数不足5人,只有3人，韩信又记下了这一排的人数。最后,令旗向上一扬,士兵们马上又变成了7列纵队,最后一排是两个人。阅兵结束,韩信叫来值日官,说:“你知道一共有多少士兵吗?”值日胀红了脸,说:“这个,我得先去查查花名册。”韩信笑道:“不用查了,一共有1073个士兵
2、。”值日官非常惊讶,说:“大将军真是神人啊,居然可以未卜先知。”韩信摇摇头,说:“我是根据士兵的队列变化算出来的。”那么,韩信是怎么算的呢?原来啊,韩信看到,士兵排成3列剩2人,排成5列剩3人,排成7列剩2人,那么,根据余数的性质,总人数除以3余2，除以5余3,除以7余2。所以,只要求出满足以上条件的1000附近的数就行了。韩信经过计算,得出这个数是1073。因此,士兵的总人数就是1073个。第二部分：习题精讲专题简析：同余这个概念最初是由伟大的德国数学家高斯发现的。同余的定义是这样的：两个整数a，b，如果它们除以同一自然数m所得的余数想同，则称a，b对于模m同余。记作：ab（mod）。读做：
3、同余于模。比如，12除以5，47除以5，它们有相同的余数2，这时我们就说，对于除数5，12和47同余，记做1247（mod5）。同余的性质比较多，主要有以下一些：性质（1）：对于同一个出书，两个数之和（或差）与它们的余数之和（或差）同余。比如：32除以5余数是2，19除以5余数是4，两个余数的和是2+4=6。“32+19”除以5的余数就恰好等于它们的余数和6除以5的余数。也就是说，对于除数5，“32+19”与它们的余数和“2+4”同余，用符号表示就是：322（mod5），194（mod5），32+192+41（mod5）性质（2）：对于同意个除数，两个数的乘积与它们余数的乘积同余。性质（3）：
4、对于同意个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。性质（4）：对于同意个除数，如果两个整数同余，那么它们的乘方仍然同余。应用同余性质几萼体的关键是要在正确理解的基础上灵活运用同余性质。把求一个较大的数除以某数的余数问题转化为求一个较小的数除以这个数的余数，使复杂的题变简单，使困难的题变容易。例题1：求199259除以7的余数。应用同余性质（2）可将199259转化为求1992除以7和59除以7的余数的乘积，使计算简化。1992除以7余4，59除以7余3。根据同余性质，“43”除以7的余数与“199259”除以7的余数应该是相同的，通过求“43”除以7的余数就可知道1992
5、59除以7的余数了。因为199259435（mod 7）所以199259除以7的余数是5。1.求4217364除以6的余数。2.求133965512除以13的余数。3.求87943765283除以11的余数。例题2：已知2001年的国庆节是星期一，求2010年的国庆节是星期几？一星期有7天，要求2010年的国庆节是星期几，就要求从2001年到2010年的国庆节的总天数被7除的余数就行了。但在甲酸中，如果我们能充分利用同余性质，就可以不必算出这个总天数。2001年国庆节到2010年国庆节之间共有2个闰年7个平年，即有“3662+3657”天。因为3662224（mod 7），3657170（mo
6、d 7），3662+365722+174+04（mod 7）答：2010年的国庆节是星期五。练习2：1.已知2002年元旦是星期二。求2008年元旦是星期几？2.已知2002年的“七月一日”是星期一。求2015年的“十月一日”是星期几？3.今天是星期四，再过365的15次方是星期几？例题3：求2001的2003次方除以13的余数。2001除以13余12，即200112（mod 13）。根据同余性质（4），可知2001的2003次方12的2003次方（mod 13），但12的2003次方仍然是一个很大的值，要求它的余数比较困难。这时的关键就是要找出12的几次方对模13与1是同余的。经试验可知12
7、的平方1（mod 13），而200321001+1。所以（12的平方）的1001次方1的1001（mod 13），即12的2002次方1（mod 13），而12的2003次方12的2002次方12。根据同余性质（2）可知12的2002次方1211212（mod 13）因为：2001的2003次方12的2003次方（mod 13）12的平方1（mod 13），而200321001+112的2003次方12的2002次方1211212（mod 13）所以2001的2003次方除以13的余数是12。练习3：1.求16的200次方除以13的余数。2.求2001的2003次方除以13余几。3.9个小朋友
8、坐成一圈，要把35的7次方粒瓜子平均分给他们，最后剩下几粒？例题4：自然数16520，14903，14177除以m的余数相同，m最大是多少？自然数16520，14903，14177除以m的余数相同，换句话说就是165201490314177（mod m）。根据同余性质（3），这三个饿数同余，那么它们的差就能被m整除。要求m最大是多少，就是求它们差的最大公约数是多少？因为1652014903=1617=37的平方111652014177=2343=31171 1490314177=726=2311的平方M是这些差的公约数，m最大是311=33。练习4：1.若2836、4582、5164、6522
9、四个整数都被同一个两位数相除，所得的余数相同。除数是多少？2.一个整数除226、192、141都得到相同的余数，且余数不为0，这个整数是几？3.当1991和1769除以某一个自然数m时，余数分别为2和1，那么m最小是多少？例题5：某数用6除余3，用7除余5，用8除余1，这个数最小是几？我们可从较大的除数开始尝试。首先考虑与1模8同余的数，91（mod 8），但9输以7余数不是5，所以某数不是9。171（mod 8），17除以7的余数也不是5。251（mod 8），25除以7的余数也不是5。331（mod 8），33除以7的余数正好是5，而且33除以6余数正好是3，所以这个数最小是33。上面的方
10、法实际是一种列举法，也可以简化为下面的格式：被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孔。问：这个圆圈上共有多少个孔？第三部分：数学史高斯有多伟大 同余这个概念最初是
11、由伟大的德国数学家高斯发现的。 高斯 （Gauss, Carl Friedrich, 1777-1855） ,德国数学家，科学家，他幼年时就表现出超人的数学天才。和牛顿、阿基米德，被誉为有史以来的三大数学家。高斯是近代数学奠基者之一，在历史上影响之大， 可以和阿基米德、牛顿、欧拉并列，有“数学王子”之称。高斯的数学研究几乎遍及所有领域，在数论、代数学、非欧几何、复变函数和微分几何等方面都做出了开创性的贡献。他还把数学应用于天文学、大地测量学和磁学的研究，发明了最小二乘法原理。高斯的数论研究总结在算术研究（1801）中，这本书奠定了近代数论的基础，它不仅是数论方面的划时代之作，也是数学史上不可多得的经典著作之一。高斯对当代数学的重要贡献是证明了代数基本定理，他的存在性证明开创了数学研究的新途径。高斯一生共发表155篇论文，他对待学问十分严谨，其着作有地磁概念和论与距离平方成反比的引力和斥力的普遍定律（1840）等。参考答案：练习1：1、 余2 2、 余8 3、余7练习2：1、星期二 2、星期四 3、星期五练习3：1、9 2、12 3、8粒练习4：1、97 2、17 3、 最小值是13练习5：1、141 2、531 3、91
