第8讲 数论(余数问题)

数论是研究整数的性质和结构的学科，它涉及了很多有趣而又重要的定理和原理。

在数论中，同余定理是一个非常基础而且重要的概念。

同余定理通过研究整数的除法运算与取余运算之间的关系，帮助我们理解整数的性质和规律。

下面我们将详细讨论同余定理的概念和其在数论中的应用。

首先，我们来了解一下同余的概念。

在数学中，同余是指整数之间满足某种特定关系的性质。

具体而言，如果两个整数除以同一个正整数所得的余数相等，则这两个整数被称为同余的。

用数学符号来表示，即对于整数a、b和正整数m，如果a与b除以m所得的余数相等，则称a与b关于模m同余，记作a≡b (mod m)。

例如，5≡11 (mod 3)，表示5与11关于模3同余。

接下来，我们来介绍同余定理及其相关概念。

同余定理是数论中的一组基本定理，它揭示了整数之间同余关系的一些基本性质。

常见的同余定理有三类：欧拉定理、费马小定理和中国剩余定理。

欧拉定理是数论中最重要的定理之一。

它是基于欧拉函数的一个结论，表明对于任意正整数a和正整数m，如果a与m互质（即它们没有公共因子），则有a^φ(m)≡1 (mod m)，其中φ(m)表示小于m且与m互质的正整数的个数。

费马小定理是同余定理中的另一个重要定理。

它是费马定理的一个特殊情况，宣称对于任意正整数a和质数p，有a^p≡a (mod p)。

这个定理常常用于证明一些数论问题，尤其是在素数的应用中经常被使用。

中国剩余定理是一组定理的集合，用于解决一类同余方程组的问题。

对于给定的一组余数和模数，中国剩余定理可以找到一个与这组余数同余的最小非负整数。

这个定理在密码学和计算机科学中有着广泛的应用，被用于构建高效的算法和数据结构。

同余定理在数论中有着重要的应用。

首先，同余定理可以帮助我们简化复杂的计算。

由于同余关系的转换性，我们可以通过将整数转换为其对模m的余数，将复杂的运算转化为简单的模运算，从而简化了问题的求解过程。

此外，同余定理还能够帮助我们证明数论问题中的一些重要结论。

小学生六年级奥数数论考点：余数问题
一、同余的定义：
①若两个整数a、b除以m的余数相同，则称a、b对于模m同余。

②已知三个整数a、b、m，如果m|a-b，就称a、b对于模m同余，记作a≡b(mod m)，读作a同余于b模m。

二、同余的性质：
①自身性：a≡a(mod m);
②对称性：若a≡b(mod m)，则b≡a(mod m);
③传递性：若a≡b(mod m)，b≡c(mod m)，则a≡ c(mod m);
④和差性：若a≡b(mod m)，c≡d(mod m)，则a+c≡b+d(mod m)，a-c≡b-d(mod m);
⑤相乘性：若a≡ b(mod m)，c≡d(mod m)，则a×c≡ b×d(mod m);
⑥乘方性：若a≡b(mod m)，则an≡bn(mod m);
⑦同倍性：若a≡ b(mod m)，整数c，则a×c≡ b×c(mod m×c);
三、关于乘方的预备知识：
①若A=a×b，则MA=Ma×b=(Ma)b
②若B=c+d则MB=Mc+d=Mc×Md
四、被3、9、11除后的余数特征：
①一个自然数M，n表示M的各个数位上数字的和，则M≡n(mod 9)或(mod 3);
②一个自然数M，X表示M的各个奇数位上数字的和，Y表示M的各个偶数数位上数字的和，则M≡Y-X或M≡11-(X-Y)(mod 11);
五、费尔马小定理：
如果p是质数(素数)，a是自然数，且a不能被p整除，则ap-1≡1(mod p)。

余数知识点总结一、余数的定义在进行整数除法时，如果被除数不能被除数整除，我们就会得到一个余数。

例如，当我们用10除以3时，商是3，余数是1，因为10除以3得到3余1。

一般来说，对于任意的整数a和b（b不为0），都存在唯一的整数q和r，使得a=bq+r，其中q是商，r是余数。

二、余数的性质1. 余数的范围余数r的范围是0到b-1。

这是因为如果r=b-1，那么a=bq+r=bq+(b-1)=(q+1)b-1。

所以当r大于等于b时，我们可以用b来替换掉r，而商q则加1。

所以余数r必然小于b。

2. 余数的相等性如果两个整数a和b除以同一个整数m得到相同的余数，那么它们的差也一定能被m整除，即如果a%m=b%m，则(a-b)%m=0。

3. 余数的加法性两个整数a和b的余数之和等于它们的和的余数，即(a+b)%m=(a%m+b%m)%m。

4. 余数的乘法性两个整数a和b的余数之积等于它们的积的余数，即(a*b)%m=(a%m*b%m)%m。

5. 余数的幂运算如果要计算a的n次幂的余数，我们可以先计算a%m的n次幂的余数，然后再对m取余。

即a^n%m=(a%m)^n%m。

6. 余数的倒数两个整数a和b互素，即它们的最大公约数是1，那么a在模b意义下一定有倒数。

即对于方程ax≡1 mod b，一定存在整数x满足条件。

三、余数的应用1. 余数的运算余数在算术运算中有着广泛的应用，可以用于简化复杂的运算。

例如在大数运算中，我们往往会对结果取模，以减小结果的数值大小，提高运算效率。

2. 余数的模运算模运算是指对一个数除以另一个数后得到的余数。

在计算机科学中，模运算常常被用于实现循环、加密和散列等操作。

例如在密码学中，模运算可以用于加解密算法中的步骤之一。

3. 余数的逆元余数的逆元是指在模意义下存在的一个数，使得与它相乘后得到的余数是1。

余数的逆元在密码学和数论中有着重要的应用，例如在RSA算法中，逆元的存在性是保证算法有效性的关键。

在做整数之间的除法时，常常会碰到不能除尽的情况。

带余除法也因此成为了数论中一块重要的组成部分。

五年级的余数问题，需要在四年级的计算基础上，掌握一些复杂的计算技巧，包括结合最小公倍数和最大公约数来计算。

同时，中国剩余定理也是非常重要的知识点。

知识点汇总中国剩余定理中国剩余定理，又称为中国余数定理、孙子定理，古有“韩信点兵”、“孙子定理”、“鬼谷算”、“隔墙算”、“剪管术”、“秦王暗点兵”、“物不知数”之名，是数论中的一个重要命题。

解题方法：1）逐步满足法。

列出一列满足一个或两个条件的数列，从中寻找第一个满足所有条件的数。

这个方法的难点在于，如何选择这个数列，能够简化我们的选择过程。

2）最小公倍数法。

该方法适用于同余的情况，或者可以转化成同余的特殊情况。

重点在于转换问题的方法。

某年的十月里有5个星期六，4个星期日，问这年的10月1日是星期几1.1.2016年4月有4个周四，5个周五，请问2016年4月12日是星期几？、星期一、星期二、星期三、星期四2.2.2015年10月23日是星期五，2015年10月有___个星期日？3.3.奶奶告诉小明：2006年共有53个星期日。

聪明的小明立刻告诉奶奶：2007年的元旦一定是星期__？（请回答一、二、三、四、五、六或日）视频描述3101除以7的余数是________1.1.2^2016除以13的余数为？(A^B表示A的B次方)2.2.若a为自然数，证明10整除a^1985- a^1949(输入0看解析)3.3.视频描述一个两位数去除251，得到的余数是41。

求这个两位数1.1.数1257除以一个三位数，余数是150，这个三位数是__？2.2.数235除以一个数的余数是30，可能的除数有哪几个？(答案中间请用一个空格隔开答案并按小到大顺序填写例:1 2)3.3.2016除以一个两位数余数为40，求出所有可能的两位数。

(答案中间请用一个空格隔开答案并按小到大顺序填写例:1 2)视频描述一个自然数除429,791,500所得的余数分别是a+5,2a和a，求这个自然数和a的值1.在除13511，13903及14589时能剩下相同余数的最大整数是__？2.2.若有一个大于1的正整数除314,257,447所得的余数相同，则2002除以这个数的余数是__？3.3.已知有一个数除309,222,251所得的余数相同，这个余数为__？视频描述一个整数除以3余2，商除以5余3，再用新的商除以7余5，则此数除以35余______1.1.一个小于200的整数除以7余3，商除以8余5，求问该数最大为多少？2.2.一个整数除以9余2，商除以3余1，再用新的商除以5余3，则此数除以45余___？3.3.一个大于50小于200的整数除以10余2，商除以7余5，求问该数可能为多少？(写出所有答案，答案中间请用一个空格隔开答案并按小到大顺序填写例:1 2)视频描述有一个整数，用它去除70，110，160所得到的3个余数之和是50，那么这个整数是______1.1.三个不同的自然数的和为2001，它们分别除以19,23,31所得的商相同，所得的余数也相同，求这三个数分别是_______,_______,_______(答案中间请用一个空格隔开答案并按小到大顺序填写例:1 2 3)2.2.有一个整数，用它去除90，50，100所得到的3个余数之和是35，那么这个整数是______．3.3.三个不同的自然数的和为2016，它们分别除以17,23,34所得的商相同，所得的余数也相同，求这三个数分别是_______,_______,_______(答案中间请用一个空格隔开答案并按小到大顺序填写例:1 2 3)在200至300之间，有三个连续的自然数，其中，最小的能被3整除，中间的能被4整除，最大的能被13整除，那么这样的三个连续自然数分别是多少？1.1.某个两位数是2 的倍数, 加1 是3 的倍数, 加2 是4 的倍数, 加1 是5 的倍数, 那么这个两位数是________(写出所有答案答案中间请用一个空格隔开答案并按小到大顺序填写例:1 2)2.2.有一个自然数用7除余3，用9除余4。

奥数数论：余数问题要点及解题技巧(总2页)-CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除奥数数论：余数问题要点及解题技巧一、基本概念：对任意自然数a、b、q、r，如果使得a÷b=q……r，且0余数，q叫做a除以b的不完全商。

二、余数的性质：①余数小于除数。

②若a、b除以c的余数相同，则c|a-b或c|b-a。

③a与b的和除以c的余数等于a除以c的余数加上b除以c的余数的和除以c的余数。

④a与b的积除以c的余数等于a除以c的余数与b除以c的余数的积除以c的余数。

三、同余的定义：①若两个整数a、b除以m的余数相同，则称a、b对于模m同余。

②已知三个整数a、b、m，如果m|a-b，就称a、b对于模m同余，记作a≡b(modm)，读作a同余于b模m。

四、同余的性质：①自身性：a≡a(modm)；②对称性：若a≡b(modm)，则b≡a(modm)；③传递性：若a≡b(modm)，b≡c(modm)，则a≡c(modm)；④和差性：若a≡b(modm)，c≡d(modm)，则a+c≡b+d(modm)，a-c≡b-d(modm)；⑤相乘性：若a≡b(modm)，c≡d(modm)，则a×c≡b×d(modm)；⑥乘方性：若a≡b(modm)，则an≡bn(modm)；⑦同倍性:若a≡b(modm)，整数c，则a×c≡b×c(modm×c)；五、被3、9、11除后的余数特征：①一个自然数M，n表示M的各个数位上数字的和，则M≡n(mod9)或（mod3）；②一个自然数M，X表示M的各个奇数位上数字的和，Y表示M的各个偶数数位上数字的和，则M≡Y-X或M≡11-（X-Y）(mod11)；六、费尔马小定理：如果p是质数（素数），a是自然数，且a不能被p整除，则ap-1≡1(modp)。

第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，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。

数论模块数论题的特点就是简洁明了，信息量看起来往往比较少，所以很多同学在见到数论题的时候总会觉得无从入手，因此，做数论题时很重要的一点就是寻找突破口，走对方向。

另外，数论模块的另一个特点就是：知识点非常多。

但相比组合而言，数论至少显得更“有法可依”，考场上一定要敢去思考数论题，“战略上藐视，战术上重视”，战略上要相信，考题所用的知识点绝对不会超出小学知识范畴，而考前我们能做的，就是好好研究一下战术——如何应对每一类题目。

我就不详细讲每一个知识点（确实非常之多，关键在于平常积累），在这里，我就解数论题的三个突破口来谈谈考场上如何找到数论题的解题思路。

还是那个我在课堂上讲过很多遍的例子：任意找一个数，我们都可以从三个角度去分析它，例如154：（1）我们可以说它是一百五十四，在这里，1是百位上的数字，它代表1个100，5代表5个10，4代表4个1，这可以说是位值原理的角度；（2）154＝2×7×11，分解质因数；（3）154除以5余4，除以9余1，我们可以研究它除以任意一个数所得的商和余数；以上三种角度分析一个数也映射出数论体系的三大块内容，同时也是我们分析数论问题的三种方式，三个突破口。

下面我来详细讲讲每一个角度。

一、位值原理和整除。

其实所有数字的整除特性都是利用位值原理推导出来的，从这个也反映出了学习数论的一个策略：找到知识点的源头，知道它们是怎么来的，这样就不用背那么多知识点了。

言归正传，什么样的题目我们往这个角度去思考呢？有些题目比较明显，就不用多说了，举个最简单的例子：55□39能被11整除，请问□是几？这种题就直接利用整除特性就OK了。

考得比较多的，比如这样的题目：“一个三位数A的三个数字所组成的最大三位数与最小三位数的差仍是数A，这个三位数A是多少？”题中提到了X位数或者提到了这个数里面的某几位数字的，可以考虑用位值原理。

利用位值原理对题目进行“翻译”——也就是把文字翻译成数学语言（数学式子），再结合其他的知识点去“加工”，一步步地解答它。