剩余定理公式及其相应的应用

《剩余定理公式及其相应的应用》由会员分享，可在线阅读，更多相关《剩余定理公式及其相应的应用（3页珍藏版）》请在金锄头文库上搜索。

1、剩余定理公式及其应用剩余定理公式及其应用把某些相关需要的部分有所增减，可以说是有点 copy 的意味，希望这样便于看懂一些定理定理 1 设设 m1,m2,mk 是两两互素的正整数，则对任意是两两互素的正整数，则对任意 b1,b2,bk，同余方程组，同余方程组x mod m1=b1 mod m1, x mod m2=b2 mod m2, Xmodmk=bkmodmk 其解为：其解为： x=(M1M1b1+M2M2b2+MkMkbk )mod m m=m1m2mk, Mi=m/mi MiMi mod mi=1 显然显然(Mi,mi)=1 即即 Mi是是 Mi 的逆元的逆元 Mi (mi)-1mod

2、 mi 或者可用辗转相除法求或者可用辗转相除法求 Mi.今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？ 解答：三三数之有二对应 140，五五数之有三对应 63，七七数之有二对应 30，这些数相 加得到 233，再减 210，即得数 23。 同余方程式：x mod 3=2x mod 5=3x mod 7=2 m1=3 m2=5 m3=7 b1=2 b2=3 b3=2m=m1m2m3=357 M1=m/m1=57 M1=Mi(mi)-1mod mi=2 M2=m/m2=37 M2=Mi(mi)-1mod mi=1 M3=m/m3=35 M3=Mi(mi)-1mod mi=1

3、 x=(M1M1b1+M2M2b2+MkMkbk )mod m =(2*5*7*2+1*3*7*3+1*3*5*2)mod 105 =(140+63+30) mod 105=233 mod 105=23例 1：一个数被 3 除余 1，被 4 除余 2，被 5 除余 4，这个数最小是几？ 题中 3、4、5 三个数两两互质。 则4，5=20；3，5=15；3，4=12；3，4，5=60。 为了使 20 被 3 除余 1，用 202=40； 使 15 被 4 除余 1，用 153=45； 使 12 被 5 除余 1，用 123=36。 然后，401452364=274， 因为，27460，所以，27

4、4604=34，就是所求的数。例 2：一个数被 3 除余 2，被 7 除余 4，被 8 除余 5，这个数最小是几？ 题中 3、7、8 三个数两两互质。 则7，8=56；3，8=24；3，7=21；3，7，8=168。 为了使 56 被 3 除余 1，用 562=112；使 24 被 7 除余 1，用 245=120。 使 21 被 8 除余 1，用 215=105； 然后，112212041055=1229， 因为，1229168，所以，12291687=53，就是所求的数。例 3：一个数除以 5 余 4，除以 8 余 3，除以 11 余 2，求满足条件的最小的自然数。 题中 5、8、11 三

5、个数两两互质。 则8，11=88；5，11=55；5，8=40；5，8，11=440。 为了使 88 被 5 除余 1，用 882=176； 使 55 被 8 除余 1，用 557=385； 使 40 被 11 除余 1，用 408=320。 然后，176438533202=2499， 因为，2499440，所以，24994405=299，就是所求的数。例 4：有一个年级的同学，每 9 人一排多 5 人，每 7 人一排多 1 人，每 5 人一排多 2 人， 问这个年级至少有多少人 ？（幸福 123 老师问的题目） 题中 9、7、5 三个数两两互质。 则7，5=35；9，5=45；9，7=63；

6、9，7，5=315。 为了使 35 被 9 除余 1，用 358=280； 使 45 被 7 除余 1，用 455=225； 使 63 被 5 除余 1，用 632=126。 然后，280522511262=1877， 因为，1877315，所以，18773155=302，就是所求的数。例 5：有一个年级的同学，每 9 人一排多 6 人，每 7 人一排多 2 人，每 5 人一排多 3 人， 问这个年级至少有多少人 ？（泽林老师的题目） 题中 9、7、5 三个数两两互质。 则7，5=35；9，5=45；9，7=63；9，7，5=315。 为了使 35 被 9 除余 1，用 358=280； 使

7、45 被 7 除余 1，用 455=225； 使 63 被 5 除余 1，用 632=126。 然后，280622521263=2508， 因为，2508315，所以，25083157=303，就是所求的数。 （例 5 与例 4 的除数相同，那么各个余数要乘的“数”也分别相同，所不同的就是最后两步。 ）例一，一个数被 5 除余 2，被 6 除少 2，被 7 除少 3，这个数最小是多少？ 解法：题目可以看成，被 5 除余 2，被 6 除余 4，被 7 除余 4 。看到那个“被 6 除余 4， 被 7 除余 4”了么，有同余数的话，只要求出 6 和 7 的最小公倍数，再加上 4，就是满足 后面条件

8、的数了，6X7446。下面一步试下 46 能不能满足第一个条件“一个数被 5 除 余 2”。不行的话，只要再 46 加上 6 和 7 的最小公倍数 42，一直加到能满足“一个数被 5 除余 2”。这步的原因是，42 是 6 和 7 的最小公倍数，再怎么加都会满足 “被 6 除余 4，被 7 除余 4”的条件。 464288464242130 46424242172例二，一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就 多四人，问这个班有多少学生？ 解法：题目可以看成，除 3 余 2，除 5 余 3，除 7 余 4。没有同余的情况，用的方法是“逐 步约束法”，就是从“除 7 余 4 的数”中找出符合“除 5 余 3 的数”，就是再 7 上一直加 4， 直到所得的数除 5 余 3。得出数为 18，下面只要在 18 上一直加 7 和 5 得最小公倍数 35，直到满足“除 3 余 2” 4711 11718 183553