怎么求被m1除余n1,被m2除余n2的数x ?例：求被143除余62被42除余18的数.
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/16 02:17:25
怎么求被m1除余n1,被m2除余n2的数x ?例：求被143除余62被42除余18的数.
怎么求被m1除余n1,被m2除余n2的数x ?例：求被143除余62被42除余18的数.
怎么求被m1除余n1,被m2除余n2的数x ?例：求被143除余62被42除余18的数.
一、先求被143整除,被42除余1的数
143M = 42N + 1
N = (143M - 1) /42 = 3M + (17M - 1)/42,显然(17M - 1)要被42整除.
即求被17整除、被42除余1的数
17M - 1 = 42T
M = (42T + 1)/17 = 2T + (8T + 1)/17,显然(8T + 1)要被17整除,
明显地T = 2,M = 5,N = 17.
被143整除,被42除余1的数 = 143*5 或 = 42*17 + 1 = 715
二、再求被42整除,被143除余1的数
42M = 143N + 1
M = (143N + 1)/42 = 3N + (17N + 1)/42,显然(17N + 1)要被42整除.
即求被42整除、被17除余16的数
17N + 1 = 42T
N = (42T - 1)/17 = 2T + (8T - 1)/17,显然(8T - 1)要被17整除.
即求被17整除、被8除余1的数
8T - 1 = 17K
T = (17K + 1)/8 = 2K + (K + 1)/8,
明显地,K = 7,T = 15,N = 37,M = 126
被42整除,被143除余1的数 = 42*126 或 = 143*37 + 1 = 5292
因此,被143除余62被42除余18的数
= 715*18 + 5292*62 = 12870 + 328104 = 340974
143、42的最小公倍数 = 143 * 42 = 6006
因此340974 加、减6006的任意倍数,仍成立.
由340974 ÷ 6006 = 56 ……4638 可知,最小的满足题意的数就是 4638.
上面是用中国剩余定理的算法,辗转求同余,最终求得.
有关算法原理参见：zhidao.baidu.com/question/42365764.html
或百度中国剩余定理、孙子定理等查看.