同余问题解题技巧

这个视频我们将会学习余数的最后一讲同余问题。 同余就是准余数相同。例如，三十一除以三余一，十六除以三也余一，因为余数都是一，那我们就说三十一和十六对三同余，同样，因为三十一除以四余三，二十三除以四也余三，那么三十一和二十三就对四同余。知道了什么是同余，那同余有什么性质呢？ 先看第一组，由于两个数除以三都余一，那么用三十一减十六的话，两个余一就抵消了，说明差是三的倍数。 而三十一减十六等于十五，正好是三的五倍。而在第二组中，用三十一减二十三得八，也是除数四的倍数。通过这两个例子可以发现，对同于的两个数做差，差 正好是除数的倍数。知道了这个结论，那我们就可以在同一问题中求除数了。例如，已知 a 大于一、七十六和三十七除以 a 的余数相同，那么 a 是多少呢？ 由于七十六和三十七对 a 同于直接对他俩做差，七十六减三十七等于三十九。根据刚才的结论，他是 a 的倍数，那 a 是三十九的因数，可以是一、三十三和三十九。 由于题目说 a 要大于一，所以不能是一，那么 a 有三种可能，三十三和三十九。 在上面的例子中，倍除数有两个可以直接做差，那如果倍除数比两个多的话，也同样是做差计算。例如，八十七、五十二和三十一除以 a 的余数相同，且 a 大于一。根据同余的性质，八十七减五十二的差三十五是 a 的倍数， 五十二减三十一的差二十一也是 a 的倍数，那么 a 是三十五和二十一的公因数，因为三十五和二十一的最大公因数是七，所以 a 是七的因数，可以是一或七，但因为 a 要大于一，所以 a 是七。好的，同一问题我们就讲到这里。

今天我们讲小学六年级奥数第三十八讲同于法解题。同于这个概念是由伟大的德国数学家高斯发现的。 高斯我们对他的了解应该是老师说谁能最先算完一加到一百的结果，谁就先出去玩。 高斯不用一分钟就算完了，等于五千零五十，他就是用等差数列求和公式，首相加末项乘项数除以二算出来的。高斯从小就有数学思维， 同于的定义是这样，如果有两个整数 ab， 比如说十二和四十七， 他们除以同一个自然数 m 比如他俩都除以五，这个 m 是除数，所得的余数是相同的。 十二除以五于二，四十七除以五也于二，他们得的余数是相同的。那么我们就说 ab 对于魔 m 同于，那咱们这道题就是十二和四十七对于魔，五同于 写，就写 a， 三行一个 b， 括号 m o， d 读魔，魔 m 读的时候就是 a 同于 b 模 m 前面三 横横左边和右边写的是被除数膜，后面写的是除数。 同于的性质比较多。我们先看第一个，对于同一个除数，两个数的和或差与他们的余数的和或差同于。举了个例子，三十二除以五，余数是二， 三十二除以五等于六于二，十九除以五，余数是四十九除以五，伤三于四， 两个余数的和二加四等于六，三十二和十九的和 等于五十一，五十一除以五，商十于一，六除以五，商一于一。所以三十二与十九的和 除以五的余数与三十二除以五，十九除以五，这两个余数的和除以五，得到的余数是相同的，这个性质就是这么个意思。 同样差也是一个道理。那我们就写作三十二加十九同于二，加四同于 一，这个一就是余数抹五。 第二个性质，对于同一个除数，两个数的乘积和他们余数的乘积也同于，还是刚才那两个数。三十二除以五， 伤六于二，十九除以五，伤三于四。其实伤几不重要，关键看余数，这两个余数的积，二乘四等于八，这两个数的积三十二乘十九等于六百零八， 六百零八除以五等于一百二十一于三，八除以五等于一于三。这两个数的 几与这两个数分别除以五之后得到的余数，然后再乘几除以五，得到的余数是相同的。可是三十二乘十九得到的这个数很大，不好算。二乘八，二乘四得八，得到的这个数除以五，非常好算。 也就是说，这两个数的和与这两个数余数的和余数相同，这两个数的基与这两个数余数的基余数也相同。 叉也是。咱们看第三个性质，对于同一个除数，如果两个与整数同于，那么他们的差一定被这个整数整除。 咱们还用刚才这个例子，三十四除以五，伤六于四，十九除以五，伤三于四， 两个余数都是四，用三十四减十九，得到的数是十五，十五一定能被五整出。 因为三十四和十九除以五都有余数，这两个余数相同，他俩减了之后，就把那个余数减没了，所以剩下的这个十五一定能被五整出。 性质，四。对于同一个除数，如果有两个整数同于，那么他们的乘方仍然同于 乘方，就是一个数。比如说三十四，这一个数就是三十四的依次方。如果两个三十四相乘，就是三十四的平方。如果有三个三十四相乘， 那就是三十四的立方，右上角这个数是个数，有多少个三十四右上角就是几。 三十四除以五，余数是四十九除以五，余数也是四。所以三十四和十九 对于五来说，余数是相同的。我把三十四平方，十九也平方， 得到的这个一千一百五十六除以五的余数，与三百六十一除以五的余数也相同，不过他的余数是一五十四了。 同样三十四的立方这么大一个数与十九的立方六千八百五十九除以五的余数也相同，而且都是四。 所以我们就发现一个数与他的基次方三十四的依次方，三十四的立方三次方一和三都是基数， 所以一个数与他的基次方的余数是相同的，与他的偶次方余数不同。如果都是偶数，比如三十四的平方和三十四的四次方余数也相同， 要么都是拘束，要么都是偶数。 我们为什么要用同于的性质呢？因为刚才这个数 三十四乘十九这个数很大，这这三十二乘十九，如果是更大的数，百位三位数乘十九，或者三位数乘三位数，那数就更大。 用这个数去除以五，就不如二乘四得八。用八除以五容易，数越小越好算。 我们用同于的性质，就是为了把较大的数除以某数的余数，转化成一个比较小的数，除以这个数的余数。下面我说一下 蜜的运算。我先说什么叫蜜，三十四的三十四的立方三十四，这个数叫底数，你就理解成他在底下，他叫底数。三，右上角这个三叫指数， 他表示有三个三十四相乘，那么这个整体我圈上的这个三十四的立方，这个整体就叫密，这个数特别大，我们不用算出来就可以这么表示。三十四的立方这么表示他就叫密。 同底数的密相乘，底数不变，指数相加三十四立方，乘三十四的平方， 底数还是三十四，指数三加二等于五。我们学了加减和乘除， 加减叫一级运算，就是最低的那个运算，最简单最低的我们最先学乘除，叫二级运算， 比加减高一级乘方叫三级运算。开方没学呢，咱们先不说他 乘方，结果就叫密，所以密相乘，这是乘号，那么它的指数运算降一级乘法，降乘加法，只 数相加三加二等于五密的乘方。如果密是按乘方算的，三十四的立方的平方 密做成方，那么底数不变。指数相乘二和三是乘的关系，比如说六的三次方的七次方， 就等于六的二十一次方，这个六的五次方乘六的七次方，五加七十二，六的十二次方。

今天我们来学习有榆树的问题列取法。我们先读题，一堆苹果过三个装一袋则多一个，过五个装一袋则多三个。这堆苹果一共有多少个？ 我们怎么解答这道题呢？我们先学一种新方法列取法，是怎么个列取呢？首先 做三个装一袋子多一个，那我们就找第十三的倍数，而且还多一个，那就有四，四加三七七加三十十加三十，三 十六，十六加三十九，十九加三二十二，二十二加三，二十五等等等等。 若五个装一袋，则多三个，那那既是五的倍数，也多三个的是哪些数呢？ 呃，分别是，五加三等于八，八加五等于十，三，十三加五等于十八，十八加五等于二十三，二十三加五 等于二十八，二十八加五等于三十三，三十三加五等于三十八，三十八加五等于四十 四十三等等等等。所以我们来看看哪些数字是最最先被这两个数重复的呢？我们来看看， 我们发现十三是最先对重复的。我们来验证一下，我们可以用十三除以三等于四代 于一个，正好符合题目要求。我们再用十三除以五等于二代， 余三个也正好符合题目要求。所以我们验证正确啊，这堆苹果一共有有十三个。

今天我们来解决一个两千年前的数学问题，出自孙子算经，今有物不知其数。三三数之剩二，五五数之剩三，七七数之剩二。问物几何翻译成现代数学， x 魔三等于二， x 魔五等于三， x 魔七等于二，求 x 的 值。这是一个同一方程组。用时钟来理解， 一个时钟有三个刻度，时针指向二的位置。第二个时钟有五个刻度，时针指向三的位置。第三个时钟有七个刻度，时针指向二的位置。问题是三个时钟时针同时指向这些位置， x 是 多少？ 答案是二十三，验证一下，二十三除以三等于七于两对，二十三除以五等于四于三对，二十三除以七等于三于二对。通解是 x 等于二十三加一百零五 k。 中国剩余定律设 m 一 m 二 m 两两互斥同于方程组， x m e 等于 a 一 x m 二等于 a 二 在 m 等于 m 一 乘以 m， 二乘以乘以 m n 下有唯一解，也就是说零到 m e 之间的解是唯一的。关键条件是魔术必须两两互斥。 g c d 米 m j 等于一对于所有 i 不 等于 j， 比如三五七两两互斥，所以可以用 crt 反例式，四和六 g c d 四六等于二不等于一，不能用标准 c 二 t。 需要扩展版本来看 c r t 的 构造过程还是刚才的问题，构造公式是， x 等于求和 ai 乘以米乘以米的逆圆， 其中 m 等于所有魔术的乘积一零五，米等于 m 除以米，米的逆圆是米摩米的逆圆。步骤一计算米， m 一 等于一百零五除以三等于三十五， m 二等于一百零五除以五等于二十一 m 三等于一百零五，除以七等于十五， 步骤二计算逆元米的逆元三五的逆元魔三三十五魔三等于二，二的逆元是两，二一的逆元，魔五二十一魔五等于一，一的逆元是一一五的逆元魔七十五魔七等于一，一的逆元是一 步骤三组合。求解， x 等于两乘，以三十五乘以两加上三乘，以二十一乘以一加上两乘，以十五乘以一等于幺四零加六十三加三十等于两百三十三，魔一零五等于二十三。和刚才的答案一致。经典应用韩信点兵，韩信让士兵排队， 三人一排于二，五人一排于三，七人一排于二。问至少有多少士兵？数学形式， x 魔三等于二， x 魔五等于三， x 魔七等于二。这不就是刚才的问题吗？看代码实现和 数组成储余数二三二 m 数组成储魔术三五七 m 等于一百零五，循环计算每一项米等于 m， 除以你 士米的逆元累加到 x， 最后返回 x 模 m， 答案是至少二十三名士兵，通解是二十三加一零五 k。 其他应用包括大数分解， rsa 加密并行计算 crt 的 完整实现 extended g c d 函数求逆元。和之前学的扩展欧几里德一样， crt 函数先计算 m 等于所有魔术的乘积，然后循环每一项计算米和逆元 t 累加到 x， 最后确保成非负时间复杂度 o n log m， 其中 m 是 所有魔术的乘积，因为每个逆元计算是 log m 的。 扩展 c r t， 魔术不互斥，当魔术不互斥时，需要用扩展 c r t。 核心思想是合并两个方程， x 模 m e 等于 a 一， x 模 m 二等于 i， 合并为 x 模，要 c m m 一 m 二等于 a。 总结一下， c r t 解决同一方程组问题， 要求魔术两两互制。构造方法是米乘一米的逆远扩展 c r t 可处理不互制情况。应用包括韩信点兵 r s a。 加密，两千年前的智慧至今仍在发光。

看这题，一个数被七除以四，被六除以三，被五除以二，这个数最少是多少？这也是一个统一问题，这样的题怎么做呢？我们把一个数看作 a， 除数不同，余数也不相同，对吧？接着我们再来看除数和余数之间有没有关系呢？七减四等于三，也就说被除数加上三就能被七整除。 六减三等于三被除数加上三就能被六整除。五减二等于三，被除数加上三也能被 倍五整除。那么这一个数呢，也就是七六五的倍数， 我们要求的是最小的速是几，对吧？那么也就是求七六五的最小公倍数七六五，两两互制，所以七乘六乘五等于 二百一，再用二百一减掉我们补进来的三，对吧？那么就是最小光倍数二百零七。做这样的题的时候呢，我们只要记住口诀，去同与补同缺，你学会了吗？

今天我们来学习同一问题，我们先读题，箱子里有若干个鸡蛋，落七个装一袋则少一个，落五个装一袋 则多四个，这个箱子里有多少个鸡蛋？而且这次让我们求里边最少有多少个鸡蛋？首先我们怎么做这道题呢？我们可以先获取信息，你看， 若七个装一袋则少一个，我们只要加上一个，就能正好装满整袋。 然后呢，若五个装一袋则多四个，你看，如果我们把它再加一，所以又能刚好装满一袋。我们想要 正确的解答这道题，我们首先要求出七和五中间的公倍数是五乘七等于三十五，就是这就是他们的最少公倍数，也就是又能被七整除，也又能被五不整除。 然后呢，我们再继续读信息，呃，落七个装一袋则少一个，也就是需要加一，落五个装一袋则多四个也要加一。然后在这里我们需要把加换成减，所以成了减一， 因为刚才加上去的实际这一是不存在的，所以用三十五减一等于三十四，这道题 so easy 的 就解出来了。我们现在来验算一下，三十四 除以七等于四于六，你看，如果把这个六装在这个袋子里，确实这个袋子是不能装满的，少一个，因为 七减六等于一，所以还少一个。后面我们接着来算，再用三十四除以五等于六， 于是也是正确的，所以我们验证正确。你看，这道看似很难的题，其实就被我们 so easy 的 解开了， 所以答一共有三十四个，大家下期再见！

今天来看一下数量关系第三十五式关于同于定理的知识点。首先了解一下同于定理的性质，就是余数的合插机决定合插机的余数。 啥意思呢？举个例子啊，你比如 a 除以七于三， b 除以七于二，那么 a 加 b 除以七，这时候是于五的，这个五就是三加二得到的。 a 减 b 除以七于一，这个一就是三减二得到的。 a 乘以 b， 再除以七是于六的，这个六就是三乘以二得到的， 这叫余数的合插机决定合插机的余数啊。来，我们再来举个例子，你比如 a 除以七余四， b 除以七余三，这时候 a 加 b 除以七，是不是余七呀？也就是四加三是七吗？对吧？余七是不是相当于于零啊？因为能被七整除吗？对吧？这时候 a 减 b 除以七是于一的，这个一就是四减三得到的， a 乘以 b 除以七，是不是余十二，四乘以三是十二吗？余十二余数比除数还要大，所以是不是相当于余五啊？也就是十二减七得到的啊？这就是我们同于定理的性质， 那他用在我们的实战类的题目中是什么样的呢？我们看一下例假，老王、老李、老周三人周一同去图书馆，已知老王每十五天去一次，老李每十六天去一次，老周每十七 天去一次。那么这三人下次相遇时是周急。那这道题其实不难啊，思路不难，如果要求的话，我去找十五、十六和十七的最小公倍数，对吧？ 找到他三个的最小公分数，其实就是十五乘以十六，再乘以十七啊，再除以周七百一，周是七天呀，对吧？然后求出来于己，我用周一加上几天就可以了，对吧？关键在计算， 十五乘以十六乘以十七，你口算是算不出来了，你需要动笔算呀。乘啊，对吧？这样就麻烦了，真正的高手他是没必要去相乘的啊，去动笔的直接瞪眼就可以了，比如我十五除以七，我知道于一， 十六除以七余二，十七除以七余三，所以他三个相乘除以七，余数就是六， 所以余数是六。周一往后推六天，那就是周日选四 d 选项。好，本期视频到此结束，喜欢视频的朋友记得帮忙点个赞哦，谢谢大家。

二年级同一问题，小明有一些糖果，用一个正方形表示，每两颗分给一个小朋友，最后多一颗，所以正方形除以二等于圆形于一， 每三颗分给一个小朋友，最后也多一颗，所以正方形除以三等于三角形于一。 从这两个等式可以看出，正方形减一既十二的倍数，也是三的倍数。画一个数轴，标出二和三的倍数，六十二和三的最小倍数，所以小明至少有六加一等于七颗糖。

所谓同于问题，就是不同的平均分得到的余数却是相同的。如提所示，有一些魔功比二十个多，比三十个少。如果五个五个的数余三个，四个四个的数也余三个。 求小白兔一共采回了多少个蘑菇。这类同于问题，建议采用列举法，既容易理解操作，又具有普遍适用性。 一只蘑菇的总数介于二十至三十个之间，五个五个的数余三个，四个四个的数也余三个。充分利用被除数等于商城除数加余数这个公式，分别列取出总数除以五余三的 和总数除以四于三的数。看，两组数量中相同的那个数就是问题要求的答案。列一个简单的统计表，先列， 再举出二十至三十之间除以五于三的数。如果商是四，得到被除数等于二十三。如果商是五，得到被除数等于二十八。 在列举出二十至三十之间除以四于三的数。如果商是五，得到被除数等于二十三。如果商是六，得到被除数等于二十七。此时观察上下两组数量中 都存在二十三这个数，说明他是满足提议的。最后规范，书写解题步骤，列个算式，四乘五加三等于二十三。写上单位和口答，解决问题。