同余问题巧解

什么是中国剩余定理？剩余定理详细解法中国数学史书上记载：在两千多年前的我国古代算书《孙子算经》中，有这样一个问题及其解法：今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。

问物几何？意思是说：现在有一堆东西，不知道它的数量，如果三个三个的数最后剩二个，如果五个五个的数最后剩三个，如果七个七个的数最后剩二个，问这堆东西有多少个？你知道这个数目吗？《孙子算经》这道著名的数学题是我国古代数学思想“大衍求一术”的具体体现，针对这道题给出的解法是：N=70×2＋21×3＋15×2-2×105＝23如此巧妙的解法的关键是数字70、21和15的选择： 70是可以被5、7整除且被3除余1的最小正整数，当70×2时被3除余2 21是可以被3、7整除且被5除余1的最小正整数，当21×3时被5除余3 15是可以被3、5整除且被7除余1的最小正整数，当15×2时被7除余2 通过这种构造方法得到的N就可以满足题目的要求而减去2×105 后得到的是满足这一条件的最小正整数。

韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

刘邦茫然而不知其数。

我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）。

中国有一本数学古书「孙子算经」也有类似的问题：「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」答曰：「二十三」术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。

民间传说着一则故事——“韩信点兵”。

秦朝末年，楚汉相争。

一次，韩信将1500名将士与楚王大将李锋交战。

苦战一场，楚军不敌，败退回营，汉军也死伤四五百人，于是韩信整顿兵马也返回大本营。

当行至一山坡，忽有后军来报，说有楚军骑兵追来。

只见远方尘土飞扬，杀声震天。

汉军本来已十分疲惫，这时队伍大哗。

韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。

他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。

韩信马上向将士们宣布：我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。

汉军本来就信服自己的统帅，这一来更相信韩信是“神仙下凡”、“神机妙算”。

于是士气大振。

一时间旌旗摇动，鼓声喧天，汉军步步进逼，楚军乱作一团。

交战不久，楚军大败而逃。

解：一个数除以3余2，除以5余3，除以7余2，求适合此条件的最小数解答: 23。

70×2＋21×3+15×2-105×2＝23那么韩信点的兵在1000-1500之间，应该是70×2＋21×3+15×2+105×9=1073在我国古代算书《孙子算经》中有这样一个问题："今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？"意思是，"一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数."这个问题称为"孙子问题".关于孙子问题的一般解法，国际上称为"中国剩余定理".如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。

术曰：“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。

以二百一十减之，即得。

凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。

余数法巧解一类多位数问题华图教育2009年三省联考中出现了这样一道试题：【例1】由1、2、3组成的没有重复数字的所有三位数之和为多少？（）A.1222B.1232C.1322D.1332对于本题，通常有以下三种解法：解1：由这三个数字组成的没有重复数字的三位数有123、132、312、321、213、231六个，简单相加可知答案为1332，因此本题应选择D。

解2：由这样3个数字组成的三位数的个数总共有336P=个，由于3个数字的地位是完全相同的，所以这3个数字在各个位数上出现的次数相同，也即在各个位数上出现6÷3=2次。

因此在各个位数上，这6个数的加和为(1+2+3)×2=12，因此这6个数的和为12×(100+10+1)=12×111=1332。

因此本题应选择D。

解3：因为1+2+3=6为“3”的倍数，所以由1、2、3组成的没有重复数字的任意三位数也能够被3整除，因此其和也能被3整除，备选项中只有D能被3整除，因此本题应选择D。

以上三种解法中，解1最平凡，操作起来也最繁琐，尤其当数字较多时，就很难进行下去；解2的操作具有可推广性，计算量小，技巧性也较强，但是思维过程显得有些“绕”，对于数学基础较差的学生不易掌握；解法3巧用数字特性，解题快捷简便，利于学生掌握，但是却存在一点不足，就是四个选项中两个或两个以上的备选项对于3同余的情况很容易出现，这时就不能唯一确定答案了。

针对解2和解3中存在的缺陷，我们加以弥补，便可得到下面两种新的解法：解4：由解2的操作过程我们可以轻松推导出这样的结论，即由n个（不同的）非零一位数组成没有重复数字的所有n位数之和是111(n个1)的倍数。

所以例1中的求和结果必为111的倍数，经验证只有选项D满足要求，因此选择D选项。

解4的方法利用从解2方法中得出的一个结论，巧用数字特性解题，思维简单机械，容易记忆掌握，而111(n个1)与3不同，备选项中出现两个或两个以上的选项能被111(n个1)整除的可能性较低，但该方法也并非尽善尽美，因为判断一个数是否为111(n个1)的倍数并没有简便的方法，需要直接作除法验证。

第8讲剩余系及其一次同余方程一、基础知识：（1）剩余系对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2, …,n-1中的某一个。

依次可将整数分成n个类（例如n＝2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。

定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,...,n-1），那么就被称为是模n的一个完全剩余系。

定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]，这m个数{0,1,2,…m-1}称为一个完全剩余系，每个数称为相应类的代表元。

例如：当m=10则,{0,1,2,3,4,5,6,7,8,9}最小非负完全{-5,-4,-3,-2,-1,0,1,2,3,4}绝对值最小{-4,-3,-2,-1,0,1,2,3,4,5}绝对值最小（一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质：①每一个整数一定包含在而且仅包含在模m的一个剩余类中②整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是p mod m= {p+km（k是整数）}③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。

这条性质用数学符号就可表示为：p mod m= q mod m p≡q（mod m）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。

这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是：0mod m，1 mod m，2 mod m，…（m―1）mod m。

在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。

中国古代方程的有趣故事在中国古代，方程是一个重要的数学问题。

虽然与现代的高等数学相比，古代的方程求解方法显得有些简陋，但是中国古代数学家们通过各种巧妙的思路和方法，解决了许多有趣的方程问题。

本文将介绍一些中国古代方程的有趣故事。

一. 古代巧妙解方程1. 割尺法解孙子定理方程孙子定理是中国古代解方程的经典方法之一。

它使用割尺法，通过画图和几何推理来求解方程。

这个方法以孙子命名，因为他在《孙子算经》一书中提到了这个方法。

孙子定理的一个有趣例子是求解“勾股数”的问题。

勾股数是指三个正整数a、b、c满足a² + b² = c²的数。

古代数学家通过割尺法发现了一些勾股数的特殊解，如(3,4,5)和(5,12,13)等。

这些解在很长一段时间内被广泛使用。

2. 陈九思法解不定方程陈九思是中国古代数学家陈景元的别名。

他提出了一种巧妙的方法来解决一类不定方程问题，被后人称为陈九思法。

陈九思法的关键思想是“取余式”和“求解式”。

通过巧妙的变换和观察，他将复杂的不定方程转化为简单的方程或同余方程，然后再求解得到结果。

这种方法在解决一些数学问题时非常有效，被广泛应用。

陈九思法让数学家们在解决问题时有了新的思路和工具，对古代方程学的发展起到了重要作用。

二. 古代方程故事的启示中国古代方程的有趣故事不仅给我们带来了快乐，还启示我们在解决问题时要注重巧妙的思路和创造性的方法。

古代数学家们虽然没有现代计算机和高级数学工具，但他们凭借智慧和勤奋，不断探索，创造出了许多独特的解题方法。

这些故事告诉我们，数学的美妙和魅力在于它的复杂性和多样性。

解决方程不仅需要严谨的逻辑思维，更需要灵活的动手能力和创造性的思维方式。

古代方程的故事还给我们带来了对数学智慧的深刻理解。

在解决问题时，我们应该注重整体思考和灵活运用各种数学方法。

只有通过不断学习和实践，我们才能更好地理解数学的奥秘，提高解题的能力。

三. 总结中国古代方程的有趣故事丰富了历史中的数学文化，展示了古代数学家们的智慧和创造力。

数学常用巧算速算法1.乘法口诀表法：常用于两个整数相乘的计算。

通过将被乘数和乘数的数字按一定顺序排列，并将交叉相乘的结果相加，可以快速计算乘积。

2. 同余定理：常用于计算大数取模的问题。

同余定理指出，如果两个整数a和b满足a ≡ b (mod m)，那么对于任意整数x和y，都有(a + x) ≡ (b + x) (mod m)和(ax + y) ≡ (bx + y) (mod m)。

3.快速幂算法：常用于计算幂运算的问题。

快速幂算法通过将指数不断折半，减少计算次数，从而实现快速计算幂运算结果。

4.多项式乘法算法：常用于计算多项式乘法的问题。

多项式乘法算法通过拆分多项式，使用快速傅里叶变换（FFT）或卷积运算进行计算，可以快速得到多项式乘法的结果。

5.高斯消元法：常用于解线性方程组的问题。

高斯消元法通过对增广矩阵进行一系列行变换，使其转化为上三角矩阵，从而得到线性方程组的解。

6.辗转相除法：常用于求最大公约数的问题。

辗转相除法通过对两个整数进行取余操作，将原问题转化为一个更小的同样结构的问题，直到得到最大公约数。

7.素数筛法：常用于求素数的问题。

素数筛法通过标记倍数的方法，从一系列候选数中筛选出素数，可以快速得到一定范围内的所有素数。

8.切割法：常用于计算几何体体积的问题。

切割法将一个复杂的几何体切割成多个简单的几何体，通过计算这些简单几何体的体积，并结合几何体的变换规则，可以快速得到复杂几何体的体积。

9.黄金分割法：常用于求解一元函数的极值问题。

黄金分割法通过逐步更新区间，选择使得函数值减小最多的点作为下一次区间的边界点，最终可以快速找到函数的极值点。

10.杨辉三角法：常用于计算组合数的问题。

杨辉三角法通过构建杨辉三角形状，将组合数的计算转化为从三角形中读取对应位置元素的问题，可以快速得到组合数的值。

以上是数学中常用的几种巧算速算法，通过运用这些算法，可以加快计算速度，提高计算效率。

第十讲：数论之余数问题余数问题是数论知识板块中另一个内容丰富，题目难度较大的知识体系，也是各大杯赛小升初考试必考的奥数知识点，所以学好本讲对于学生来说非常重要。

许多孩子都接触过余数的有关问题，并有不少孩子说“遇到余数的问题就基本晕菜了！”余数问题主要包括了带余除法的定义，三大余数定理（加法余数定理，乘法余数定理，和同余定理），及中国剩余定理和有关弃九法原理的应用。

知识点拨：一、带余除法的定义及性质：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≤r＜b；我们称上面的除法算式为一个带余除法算式。

这里：r=时：我们称a可以被b整除，q称为a除以b的商或完全商(1)当0r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商(2)当0一个完美的带余除法讲解模型:如图，这是一堆书，共有a本，这个a就可以理解为被除数，现在要求按照b本一捆打包，那么b就是除数的角色，经过打包后共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。

这个图能够让学生清晰的明白带余除法算式中4个量的关系。

并且可以看出余数一定要比除数小。

二、三大余数定理：1.余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。

例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。

例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2.2.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。

当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。

中国剩余定理1、余同加余【例题1】一个数除以3余2，除以7余2，求这个数。

【解析】因为这个数减去2能被3整除，能被21整除，也就是21的倍数。

所以这个数为21的倍数加上2.2、差同减差【例题2】一个数除以3余1，除以7余5，求这个数。

【解析】因为这个数加上2能被3整除，能被7整除，也就是21的倍数，所以这个数为21的倍数减去2.3、和同加和【例题3】一个数除以3余2，除以4余1，求这个数。

【解析】因为这个数除以3余2，除以4余1，最小的为5，所以这个数为12的倍数加上5.剩余定理－－巧解国考行测数学题余数问题国考真题：一个三位数除以9余7，除以5余2，除以4余3，这样的三位数共有：( )A.5个B.6个C.7个D.8个论坛里面有高手分析并且解决了余数定理的问题，可是对于我们这些新手或“低手”来说，也许说的不是很容易懂。

我在这里就献丑了——高手不用看了，跳过吧。

这是专门写给新手的：先看【一】：15÷7=2……余1，即2×15÷7=4 (2)3×15÷7=6 (3)4×15÷7=8 (4)5×15÷7=10 (5)6×15÷7=12……余6. (废话？不要急，如果是新手就要慢慢看，你也可以直接做下面的例子1－4)你得出什么规律了？比如说35/3余2，那么知道70/3余“4”，也就是余1.。

35/4余3，那么70/4余“6”，也就是余2。

接着看【二】：从758里连续减去若干个105后，求所得的要求小于105的差数，实际上就是求758除以105所得的余数.即758÷105=7……余23. （废话吧？定义来着。

）结论：从某数A中连续减去N个B后，求所得的要求小于数B的差数，实际上就是求数A除以数B所得的余数.再看【三】：“孙子问题”.“一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数.”思路一：分别写出除数3、5、7的两两最小公倍数——15， 35， 21.如下所示：除以7余2的较小数——30；（3跟5的最小公倍数为15，除以7余1，由上面废话一已经知道15×2除以7余2）除以5余3的较小数——63；（21除以5余1，那么由废话一可知21×3即63，它除以5余3，下同）除以3余2的较小数——35.根据和的整除性，可知30+63+35=128一定是一个同时满足“被3除余2，被5除余3，被7除余2”的数（稍做解释：比如，63，35是7的倍数了，加起来被7除肯定是余“0”的，只有30除以7余数2还在），但是不一定是最小的.要得到满足条件的最小数，只要从中减去3、5、7的最小公倍数的若干倍，使得差数小于这个最小公倍数就是了（就是上面的废话二）. 。

第8讲剩余系及其一次同余方程一、基础知识：（1）剩余系对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2, …,n-1中的某一个。

依次可将整数分成n个类（例如n＝2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。

定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,...,n-1），那么就被称为是模n的一个完全剩余系。

定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]，这m个数{0,1,2,…m-1}称为一个完全剩余系，每个数称为相应类的代表元。

例如：当m=10则,{0,1,2,3,4,5,6,7,8,9}最小非负完全{-5,-4,-3,-2,-1,0,1,2,3,4}绝对值最小{-4,-3,-2,-1,0,1,2,3,4,5}绝对值最小（一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质：①每一个整数一定包含在而且仅包含在模m的一个剩余类中②整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是p mod m= {p+km（k是整数）}③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。

这条性质用数学符号就可表示为：p mod m= q mod m p≡q（mod m）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。

这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是：0mod m，1 mod m，2 mod m，…（m―1）mod m。

在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。