有关中国剩余定理
有关中国剩余定理
个除以3余1,除以4余2,除以5余4,求满足条件的最小的自然数?
解析:使用剩余定理的解法是：
第一个数:能同时被3和4整除,但除以5余4,即12×2=24
第二个数:能同时被4和5整除,但除以3余1,即20×2=40
第三个数:能同时被5和3整除,但除以4余2,即15×2=30
3、4、5的最小公倍数60
所以24+40+30-60=34
请问,12×2=24,20×2=40,15×2=30中的乘数2是怎么得出来的呢?
同样道理，另一个数，除以9余5，除以7余1，除以5余2，求最小值。
第一个数:能同时被9和7整除,但除以5余2,即63×4=252
第二个数:能同时被7和5整除,但除以9余5,即35×4=140
第三个数:能同时被5和9整除,但除以7余1,即45×5=225
5、7、9的最小公倍数315
所以252+140+225-315=302
问题中的×2与补充问题中的×4，×5的解释最好可以相通。
2楼的回答只能具体代入题干中的问题，不能扩展到其它的题目中……
要广义的解释这个数的话，难道要采取1楼的一个一个代入法了？
希望各位大虾不啬指教！
为了方便用X≡a(mod m)表示X用m除余数为a,aX≡b(mod m) 表示aX用m除余数为b,这称为同余式,那么两题如下去
1．求X满足同余式组
X≡1(mod3),X≡2(mod4),X≡4(mod5),
先求X1,X2,X3,它们分别满足同余式
20X1≡1(mod3),15X2≡2(mod4),12X3≡4(mod5),
（20=4×5,15=3×5,12=3×4）
解得X1≡2(mod3),X2≡2(mod4),X3≡2(mod5),（如何解下面讲）
求得上面三个同余式均是2,3个2是巧合,
故得X≡20×2+15×2+12×2≡94(mod60),X=34.
2．求X满足同余式组
X≡5(mod9),X≡1(mod7),X≡2(mod5),
先求X1,X2,X3,它们分别满足同余式
35X1≡5(mod9),45X2≡1(mod7),63X3≡2(mod5),
解得X1≡4(mod9),X2≡5(mod7),X3≡4(mod5),
故得X≡35×4+45×5+63×4≡617(mod315),X=302.
如何求同余式20X1≡1(mod3),15X2≡2(mod4),12X3≡4(mod5),等等,对你们中学生来说用尝试法即可,只要3,4,5互质（9,7,5互质）,同余式必有解,如12X≡4(mod5),将X=1,2,...,5代入尝试,X=1时,12X用5除余2,X=2,12X用5除余4,故X=2是解,尝试法计算量不大,m=5,最多尝试5次,m=9,最多尝试9次,如35X≡5(mod9),最多尝试9次,将X=1,2,3,…,9代入即可,如果你不想用尝试法,方法很多,但不如尝试法来的简单,如计算12X≡4(mod5),（1）一种是求不定方程,12X≡4(mod5)等价于求二元不定方程的整数解12X-5Y=4,可用欧几里得辗转相除法来求.
（2）先求12X≡1(mod5)的解,利用欧拉定理（这是数论重要定理a^(p-1)≡1(modp)）直接求得X≡12^(5-2) (mod5),X≡12^3 ≡2^3=8≡3,12X≡4(mod5)的解为X≡4×3≡2(mod5),这种方法求同余式aX≡b(modm)要求a,m互素.
可参看看我写的一篇文章：