同余法解题

同余法解题集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。

同余的定义是这样的：两个整数，a,b,如果他们同时除以一个自然数m，所得的余数相同，则称a,b对于模m同余。

记作a≡b（mod.m）。

读作：a同余于b模m。

同余的性质也比较多，主要有以下一些：1..对于同一个除数，两个数的乘积与它们余数的乘积同余。

例如201×95的乘积对于除数7，与201÷7的余数5和95÷7的余数4的乘积20对于7同余。

2..对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。

例如519和399对于一个除数同余，那么这个除数一定是519与399的差的因数，即519与399的差一定能被这个除数整除。

3..对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。

例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余，当然余数大小随次方变化。

4．对于同一个除数，若三个数a≡b（mod m），b≡c（mod m），那么a,b,c三个数对于除数m都同余（传递性）例如60和76同余于模8，76和204同余于模8，那么60,76,204都同余于模8。

5. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么a±c≡c±d （mod m），（可加减性）6. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么ac≡cd（mod m），（可乘性）二、中国剩余定理解法一个数被3除余1，被4除余2，被5除余4，这个数最小是几？解法：求3个数：第一个：能同时被3和4整除，但除以5余4，即12X2＝24第二个：能同时被4和5整除，但除以3余1，即20X2＝40第三个：能同时被3和5整除，但除以4余2，即15x2＝30这3个数的最小公倍数为60，所以满足条件的最小数字为24＋40+30-60=3412X2＝24 20X2＝40 15x2＝30中2的来历。

五年级奥数培训资料第六讲同余法解题一、同余这个概念最初就是由德国数学家高斯发明得。

同余得定义就是这样得: 两个整数,a,b,如果她们同时除以一个自然数ｍ,所得得余数相同,则称ａ,b对于模m同余。

记作a≡b(moｄ.ｍ)、读作:a同余于ｂ模ｍ。

同余得性质也比较多,主要有以下一些: 1、.对于同一个除数,两个数得乘积与它们余数得乘积同余。

例如20１ ×９5得乘积对于除数7,与2０1÷７得余数5与95÷７得余数４得乘积20对于7同余。

2.、对于同一个除数,如果有两个整数同余,那么它们得差就一定能被这个除数整除。

例如51９与３99对于一个除数同余,那么这个除数一定就是519与3９9得差得因数,即５19与399得差一定能被这个除数整除。

３..对于同一个除数,如果两个数同余,那么她们得乘方仍然同余。

例如２0与29对于一个除数同余,那么2０得任何次方都与２9得相同次方对于这个除数同余,当然余数大小随次方变化。

4、对于同一个除数,若三个数a≡b(moｄm),ｂ≡c(moｄm),那么a,b,ｃ三个数对于除数m都同余(传递性)例如６０与7６同余于模８,76与204同余于模８,那么60,76,204都同余于模８、5。

对于同一个除数,若四个数ａ≡ｂ(mｏdｍ),ｃ≡d(mｏd m),那么a±ｃ≡c±d(mod m),(可加减性)6。

对于同一个除数, 若四个数a≡b(mod m),c≡ｄ(modｍ),那么ac≡cｄ(mｏd m),(可乘性)二、中国剩余定理解法一个数被3除余1,被4除余2,被5除余4,这个数最小就是几?解法:ﻫ求３个数:第一个:能同时被3与4整除,但除以5余4,即１2X2=2４ﻫ第二个:能同时被４与5整除,但除以３余1,即20X2＝40第三个:能同时被3与5整除,但除以4余2,即15x2＝30ﻫ这3个数得最小公倍数为6０, 所以满足条件得最小数字为24+４0+30-60=３412X2=24 20Ｘ2＝４０15x2＝30中2得来历。

学科教师辅导讲义学员编号：年级：六年级课时数：3学员姓名：辅导科目：奥数学科教师：授课主题第27讲——同余法解题授课类型T同步课堂P实战演练S归纳总结余数问题主要包括了带余除法的定义，三大余数定理（加法余数定理，乘法余数定理，教学目标和同余定理），及中国剩余定理和有关弃九法原理的应用。

授课日期及时段T（Textbook-Based）——同步课堂知识梳理一、带余除法的定义及性质一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≤r＜b；我们称上面的除法算式为一个带余除法算式。

这里：(1)当0r=时：我们称a可以被b整除，q称为a除以b的商或完全商(2)当0r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商二、三大余数定理：1.余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。

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

2.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

3.同余定理若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：a≡b ( mod m )，左边的式子叫做同余式。

若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除用式子表示为：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整数，即m|(a－b)三、中国剩余定理1.中国古代趣题韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

刘邦茫然而不知其数。

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

同余方程与模方程的解法一、同余方程在数论中，同余方程是指形如ax ≡ b (mod m) 的方程，其中 a、b、m 为整数。

解同余方程的方法有多种，下面将介绍两种常用的解法。

1. 穷举法：穷举法是最简单直观的解同余方程的方法之一。

具体步骤如下：（1）列出满足条件的整数集合。

根据同余的定义，我们知道 x 和 b 对 m 取余数是相同的，即 x 和 b 在模 m 意义上是相等的。

因此，我们可以列出一个整数集合 S，其中的元素 x 满足x ≡ b (mod m)。

（2）从集合中选出满足条件的解。

根据具体的题目要求，我们可以从集合 S 中选出满足方程的解。

2. 扩展欧几里得算法：扩展欧几里得算法是一种高效解同余方程的方法。

它利用了欧几里得算法的思想，通过递归求解，最终得到同余方程的解。

具体步骤如下：（1）求解递归基。

如果 b = 0，则方程变为ax ≡ 0 (mod m)，此时方程的解为 x = m / (a, m)，其中 (a, m) 表示 a 和 m 的最大公因数。

（2）求解通解。

如果b ≠ 0，则根据同余方程的性质可知，ax ≡ b (mod m) 的解与 ax ≡ 1 (mod m) 的解具有相同的形式。

因此，我们可以利用扩展欧几里得算法求解 ax + my = (a, m)，其中 y 是方程ax ≡ 1 (mod m) 的一个解。

（3）求解特解。

根据通解的形式，我们可以求解出 ax + my = (a, m) 的一个特解 x0。

然后，利用 x = x0 * (b / (a, m))，即可求得同余方程的特解。

二、模方程模方程是指形如x² ≡ a (mod m) 的方程，其中 a、m 为整数。

解模方程的方法有多种，下面将介绍两种常用的解法。

1. 勒让德符号和二次互反律：勒让德符号是数论中的一个重要概念，它用来判断二次剩余和二次非剩余。

对于模方程x² ≡ a (mod p)（p 是奇素数），可以利用勒让德符号判断 a 是否是模 p 的二次剩余。

浅谈初等数论中同余式的解法
初等数论是数学的一个分支，主要探讨整数、有理数和代数式等基础概念。

“同余”是初等
数论中概念的一个重要部分，它引用数学定义可以写为：若两个有理数或者有理函数在一
个事件上有相同的值，则它们称为“同余”。

也就是说，两个有理数或者有理函数的值不同，但它们的值是相等的。

同余的解法首先应该把同余方程写成有理函数的形式，然后进行求解。

一般可以使用图像法、合并法或者二分法来求解。

图形法是一种直观清晰的求解方法，它通过在坐标系中绘制图像来求解同余方程，从而得到所求解的值。

这是最简单也是最容
易理解的求解方法。

合并法是一种基于数学运算技巧的求解方法。

它通过合并两个同余方程来求解同余方程，得到所求的值。

二分法是运用有理数的属性来求解的方法，用二分的方法对有理数的值进行查找，来获得有理数的值。

以上就是同余的几种常用方法，虽然每种方法都有其优势和缺点，但它们都是多元素的有理函数。

使用正确的方法，可以对同余
方程进行快速准确的求解，以解决初等数论中的多元素有理函数问题。

六年级奥数同余的解题规律知识六年级奥数同余的解题规律知识六年级奥数知识：同余的解题规律在作除法运算时，我们有这样的经验：(1)一些不同的数除以一个相同的数可能会得到相同的余数.如，除以5余3的数有5×1+3=8，5×2+3=13，5×3+3=18，5×4+3=23，…………(2)一个相同的'数除以一些不同的数，可能会有相同的余数.如，389分别除以5、7和11会得到相同的余数4.389÷5=77 (4)389÷7=55 (4)389÷11=55 (4)由此，我们可以来讨论下面的两个问题.某数被5除余4，被7除也余4，被11除还余4.要求某数和某数最小是多少?读者一定会想到有：5×7×11+4=389，5×7×11×2+4=774，5×7×11×3+4=1159，…………答案有无数多个，但最小的只能是389.现在，我们把这个问题上升到一般形式.问题一某数分别除以a、b、c、……，都得到相同的余数k.求某数最小是多少?聪明的读者，能得出答案吗?需要请读者注意的是，382、767、1152分别除以5、7和11所得的余数2、4、8，虽然都不相同，但是都与相应的除数相差同样多.即5-2=3，7-4=3，11-8=3.于是，我们也可以提这样的问题：某数被5除余2，被7除余4，被11除余8.问某数是多少和某数最小是多少?读者一定会想到是5×7×11×1-3=382，5×7×11×2-3=767，5×7×11×3-3=1152，…………答案有无数多个，但最小只能是382.这个问题的一般形式是：问题二某数分别除以a、b、c、……得数相应的余数分别是A、B、C、……，并且，这些余数跟相应的除数都相差同样多(也设为k)，即a-A=b-B=c-C=……=k.求某数最小是多少?聪明的读者，能得出答案吗?【规律】某数分别除以a、b、c、……，都得到相同的余数k.求某数最小是多少?答案是[a，b，c，……]+k.某数分别除以a、b、c、……，得到相应的余数A、B、C、……，并且这些余数跟相应的除数都相差同样多(设为k)，即a-A=b-B=c-C=……=k.求某数最小是多少?答案是[a，b，c，……]-k.【练习】1.某数分别除以3、5和7，都有相同的余数2.求某数最小是多少?(2除外)2.某数被5、6、7除，都得到相同的余数1.问某数在1000以内有哪几个答案?3.某数用5除余3，用7除余5，用9除余7，用11除余9.求某数最小是多少?4.某数分别用5、7、9和11除，刚好都是差3才能整除.求某数最小是多少?5.某数被2000除，余1993;被1999除，余1992;被1998除，余1991.求某数最小是多少?。

同余法解题（进阶）知识精讲例题1 求1992×59除以7的余数。

练习1 求4217×364除以6的余数。

例题2 已知2001年的国庆节是星期一，求2010年的国庆节是星期几？练习2 已知2002年元旦是星期二。

求2008年元旦是星期几？例题3 求2001的2003次方除以7的余数。

（费尔马小定理：某数的6次方除以7，余数为1）练习3 求12的200次方除以7的余数。

例题4 自然数300，262，205除以m的余数相同，m最大是多少？练习4 1.一个整数除226、192、141都得到相同的余数，且余数不为0，这个整数是几？2.有一个整数，用它去除63、91、129得到三个余数的和是25，这个整数是多少？例题5 某数用6除余3，用7除余5，用8除余1，这个数最小是几？练习5 某数除以7余1，除以5余1，除以12余9。

这个数最小是几？挑战极限例6 当1991和1769除以某一个自然数m时，余数分别为2和1，那么m最小是多少？例7在一个圆圈上有几十个孔（如图38-1），小明像玩跳棋那样从A孔出发沿逆时针方向每隔几个孔跳一步，希望一圈以后能跑回A孔，他先试着每隔2孔跳一步，也只能跳到B孔。

最后他每隔6孔跳一步，正好跳回A孔。

问：这个圆圈上共有多少个孔？课内练习1.求1339655×12除以13的余数。

2.求879×4376×5283除以11的余数。

3.已知2002年的“七月一日”是星期一。

求2015年的“七月一日”是星期几？4.2004的2004次方除以7的余数是多少？5.某数除以7余6，除以5余1，除以11余3，求此数最小值。

6.一个小于200的数，它除以11余8，除以13余10，这个数是多少？7.A除以5余1，B除以5余4，如果3A大于B,那么3A-B除以5的余数是多少？8.若442、297、210都被同一个数相除，所得的余数相同。

这个除数最大是多少？9.有一个自然数，用它分别除63,90,130，都有余数，三个余数的和为25，这三个余数中最小的一个是多少？10.号码分别为101, 126，173, 193的四个运动员进行乒乓球比赛，规定每两人比赛的盘数是他们号码的和被3除所得的余数，那么打球盘数最多的运动员打了多少盘？。

同余及余数问题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的余数为22.余数的加法定理a与b的差除以c的余数，等于a,b分别除以c的余数之差。

例如：23，16除以5的余数分别是3和1，所以23－16＝7除以5的余数等于2，两个余数差3－1＝2.当余数的差不够减时时，补上除数再减。

例如：23，14除以5的余数分别是3和4，23－14＝9除以5的余数等于4，两个余数差为3＋5－4＝43.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。

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

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

例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2.乘方：如果a与b除以m的余数相同，那么n a与n b除以m的余数也相同．一、同余定理1、定义整数a和b，除以一个大于1的自然数m所得余数相同，就称a和b对于模m同余或称a和b在模m下同余，即a≡b（modm）2、同余的重要性质及举例。

〈1〉a≡a（modm）（a为任意自然）；〈2〉若a≡b（modm），则b≡a（modm）〈3〉若a≡b（modm），b≡c（modm）则a≡c（modm）；〈4〉若a≡b（modm），则ac≡bc（modm）〈5〉若a≡b（modm），c≡d（modm），则ac=bd（modm）；〈6〉若a≡b（modm）则an≡bm（modm）其中性质〈3〉常被称为"同余的可传递性"，性质〈4〉、〈5〉常被称为"同余的可乘性，"性质〈6〉常被称为"同余的可开方性"注意：一般地同余没有"可除性"，但是：如果：ac=bc（modm）且（c，m）=1则a≡b（modm）3、整数分类：〈1〉用2来将整数分类，分为两类：1，3，5，7，9，……（奇数）；0，2，4，6，8，……（偶数）〈2〉用3来将整数分类，分为三类：0，3，6，9，12，……（被3除余数是0）1，4，7，10，13，……（被3除余数是1）2，5，8，11，14，……（被3除余数是2）〈3〉在模6的情况下，可将整数分成六类，分别是：0（mod6）：0，6，12，18，24，……1（mod6）：1，7，13，19，25，……2（mod6）：2，8，14，20，26，……3（mod6）：3，9，15，21，27，……4（mod6）：4，10，16，22，29，……5（mod6）：5，11，17，23，29，……一个三位数除以36，得余数8，这样的三位数中，最大的是__________71427和19的积被7除，余数是几?有三个自然数a ，b ，c ，已知b 除以a ，得商3余3；c 除以a ，得商9余11。

同余问题（一）差同减差，和同加和，余同取余，最小公倍加”这是同余问题的口诀。

所谓同余问题，就是给出“一个数除以几个不同的数”的余数，反求这个数，称作同余问题。

首先要对这几个不同的数的最小公倍数心中有数，下面以4、5、6为例，请记住它们的最小公倍数是60。

1、差同减差：用一个数除以几个不同的数，得到的余数，与除数的差相同，此时反求的这个数，可以选除数的最小公倍数，减去这个相同的差数，称为：“差同减差”。

例：“一个数除以4余1，除以5余2，除以6余3”，因为4-1=5-2=6-3=3，所以取-3，表示为60n-3。

【60后面的“n”请见4、，下同】2、和同加和：用一个数除以几个不同的数，得到的余数，与除数的和相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的和数，称为：“和同加和”。

例：“一个数除以4余3，除以5余2，除以6余1”，因为4+3=5+2=6+1=7，所以取+7，表示为60n+7。

3、余同取余：用一个数除以几个不同的数，得到的余数相同，此时反求的这个数，可以选除数的最小公倍数，加上这个相同的余数，称为：“余同取余”。

例：“一个数除以4余1，除以5余1，除以6余1”，因为余数都是1，所以取+1，表示为60n+1。

4、最小公倍加：所选取的数加上除数的最小公倍数的任意整数倍（即上面1、2、3中的60n）都满足条件，称为：“最小公倍加”，也称为：“公倍数作周期”。

在平时解题中，我们经常会遇到把着眼点放在余数上的问题。

如：现在时刻是7时30分，再过52小时是几时几分？我们知道一天是24小时，，也就是说52小时里包含两个整天再加上4小时，这样就在7时30分的基础上加上4小时，就是11时30分。

很明显这个问题的着眼点是放在余数上了。

1. 同余的表达式和特殊符号37和44同除以7，余数都是2，把除数7称作“模7”，37、44对于模7同余。

记作：（mod7）“”读作同余。

一般地，两个整数a和b，除以大于1的自然数m所得的余数相同，就称a、b对于模m同余，记作：2. 同余的性质（1）（每个整数都与自身同余，称为同余的反身性。

精心整理五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。

同余的定义是这样的：?两个整数，a,b,如果他们同时除以一个自然数m，所得的余数相同，则称a,b对于模m同余。

记作a≡b（mod.m）。

读作：a同余于b模m。

?同余的性质也比较多，主要有以下一些：1..对于同一个除数，两个数的乘积与它们余数的乘积同余。

例如201?×95的乘积对于除数7，与201÷7的余数5和95÷7的余数4的乘积20对于7同余。

2..对于同一个除数，如果有两个整数同余，那么它们的差就一?定能被这个除数整除。

? 例如519和399对于一个除数同余，那么这个除数一定是519与399的差的因数，即519与399的差一? 定能被这个除数整除。

?3..对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。

例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余，当然余数大小随次方变化。

??4．对于同一个除数，若三个数a≡b（mod m），b≡c（mod m），那么a,b,c三个数对于除数m都同余（传递性）例如60和76同余于模8，76和204同余于模8，那么60,76,204都同余于模8。

5. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么a±c≡c±d （mod m），（可加减性）6. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么ac≡cd（modm），（可乘性）二、中国剩余定理解法一个数被3除余1，被4除余2，被5除余4，这个数最小是几？解法：求3个数：第一个：能同时被3和4整除，但除以5余4，即12X2＝24第二个：能同时被4和5整除，但除以3余1，即20X2＝40第三个：能同时被3和5整除，但除以4余2，即15x2＝30这3个数的最小公倍数为60，所以满足条件的最小数字为24＋40+30-60=3412X2＝24 20X2＝40 15x2＝30中2的来历。