中国剩余定理新解法
温柔似野鬼°
571次浏览
2021年01月26日 06:15
最佳经验
本文由作者推荐
关于时间的谚语-
中国剩余定理新解法
一门完美的学科，应该让人们正反两面运用自如．中 国剩余定理也是如此，
正面计算具体数，
反面计算剩余数，
都能体现算术的唯一性和必 然性，
这就是我
们研究中国剩余定理的目的．
本文的计算方法属于本人独创，
其方法比教科书中
传统的倍分法简单，方便．欢迎你用其它任何方法进行比较．
我们 把中国剩余定理，
分为两类题：
简单型和复杂型，
简单型指除数都是不
同的素 数，
复杂型指除数中存在合数和素数，
当你看了本文后，
你就能够解中国
剩余 定理中的任意题型．如果，你认为本文中的解法，确实简单方便，请你转告
你的朋友．谢谢！
一，简单型
简单型指除数都是不同的素数，简单型不存在错题，解题前不必审题。
例：
M/31
余
24
，
M/37
余
36
，
M/ 41
余
10
，
M/43
余
5
，
M/47< br>余
9
，
M/53
余
15
，
M/59
余
21
，
M/61
余
23
，求
M
＝？
因为，该题的除数都是不同的素数，其余数不会存在矛盾，为有解之题，而
且，解法相当 简单．
因除数
31*37*41*43*47*53*59*61
＝
549
，即满足条件的最小
数，在除数的最小公倍数
549
之内有解，有唯 一的解．又因除数
31
＋
37
＋
41
＋
43
＋
47
＋
53
＋
59
＋
61
＝
372
，
是在
549
之内一个一个数试
除，
来寻找这个数呢 ？还是在
372
个数中寻找这个数？这就是中国剩余定理的奥
妙．
本人的解法是：滚雪球和数列化简配合使用，在
372
个数内解
549
之内的 任意数，即在
549
内取任意一个整数，除以
这
8
个素数，
把余数记下来，
按下面的方法都能够从
372
个数内准确地寻找到这
个数．< br>
1
，满足除以
61
余
23
，为等差数列
2 3
＋
61
Ｎ；
2
，将数列中的
23
和< br>61
同时除以
59
，得余数
23
和
2
，即将
23
＋
61
Ｎ化简
为
23
＋
2
Ｎ 寻找相同余数的项
(
下同
)
，取
59
项
(
一个循环周期
)
之内：
23
，
25
，
27
，
29
，
31
，
33
，
35
，
3 7
，
39
，
41
，
43
，
45
，
47
，
49
，
51
，
53
，
55
，
57
，
0(
满或
超过除数
59
时，减< br>59
再加，下同
)
，
2
，
4
，
6< br>，
8
，
10
，
12
，
14
，
16
，
18
，
20
，
22
，
24
，
26
，
28
，
30
，
32
，
34
，
36
，
38
，
40
，
42
，
44
，
46
，
48
，
50
，
5 2
，
54
，
56
，
58
，
1
，< br>3
，
5
，
7
，
9
，
11
，
13
，
15
，
17
，
19
，
21 (59
项内，没有一个重复余数，
这就是中国剩余定理的唯一性和必然性，
下面一样的 道理
)
．
得第
59
项满足除以
59
余
21
的条件，代入原等差数列
23
＋
(59-1)*61
＝
35 61
，因
61*59
＝
3599
，得
新等差数列
3 561
＋
3599
Ｎ；
3
，
将数列中的
3561
和
3599
同时除以
53
，
得余数
10< br>和
48
，
即将
3561
＋
3599
Ｎ化简为
10
＋
48
Ｎ取
53
项
(
一个循环周期< br>)
内寻找相同的余数项：
10
，
5
，
0
，< br>48
，
43
，
38
，
33
，
28< br>，
23
，
18
，
13
，
8
，
3
，
51
，
46
，
41
，
36
，
31
，
26
，
21
，
16
，
1 1
，
6
，
1
，
49
，
44
，39
，
34
，
29
，
24
，
19，
14
，
9
，
4
，
52
，
4 7
，
42
，
37
，
32
，
27
，
22
，
17
，
12
，
7
，
2，
50
，
45
，
40
，
35
，
30
，
25
，
20
，
15
，得第
53< br>项满足除以
53
余
15
的条件，代入原等差数列
3561＋
3599(53-1)
＝
190709
，因
3599*53< br>＝
190747
，
得新等差数列
190709
＋
19 0747
Ｎ；
4
，将上面数列化简为
30
＋
21
Ｎ，取
47
项之内：
30
，
4
，
25，
46
，
20
，
41
，
15
，
36
，
10
，
31
，
5
，
26
，
0
，
21
，
42
，
16
，
37
，
11
，
32
，
6
，
27
，1
，
22
，
43
，
17
，
38
，
12
，
33
，
7
，
28
，
2
，
23
，
44
，
18
，
39
，< br>13
，
34
，
8
，
29
，
3
，
24
，
45
，
19
，
40
，
14
，
35
，
9
，得第
47
项 满足条件，代入原等差数列
190709
＋
190747(47-1)
＝8965071
，因
190747*47
＝
8965109
，得 新等差数列
8965071
＋
8965109
Ｎ；
5，将上面数列化简为
1
＋
39
Ｎ，取
43
项内：
1
，
40
，
36
，
32
，
28
，
24
，
20
，
16
，
12
，
8
，
4
，
0
，
39
，
35
，
31
，
27
，
23
，
19
，
15
，
11
，
7
，
3
，
42
，
38
，
34
，
30
，
26
，
22
，< br>18
，
14
，
10
，
6
，
2
，
41
，
37
，
33
，
29
，
25
，
21
，
17
，
13
，
9
，
5
，得第
43
项满足条件，代入原等差数列
8965071
＋
8965109(43-1)
＝
385499649
，因
8965 109*43
＝
385499687
，得新等差数列
385499649＋
385499687
Ｎ；
6
，将上面数列化简为
1 9
＋
16
Ｎ，取
41
项内：
19
，
35< br>，
10(
出现相同的余数
为止
)
，得第
3
项 满足条件，代入原等差数列
385499649
＋
385499687(3-1)＝
1156499023
，因
385499687*41
＝
，得新等差数列
1156499023
＋
Ｎ；
7< br>，将上面数列化简为
13
＋
31
Ｎ，取
37
项内：< br>13
，
7
，
1
，
32
，
26
，
20
，
14
，
8
，
2
，
33
，
27
，
21
，
15
，
9
，3
，
34
，
28
，
22
，
16
，
10
，
4
，
35
，
29
，
2 3
，
17
，
11
，
5
，
36
，得 第
28
项满足条件，代入原等差数列
1156499023
＋
(28 -1)
＝
427904652532
，因
*37
＝
5848 03025179
，得新等差数列
427904652532
＋
584803 025179
Ｎ；
8
，将上面数列化简为
4
＋
1 4
Ｎ，取
31
项内：
4
，
18
，
1
，
15
，
29
，
12
，
26
，
9
，
23
，
6
，
20
，
3
，17
，
0
，
14
，
28
，
11
，
25
，
8
，
22
，
5
，
19
，
2
，
16
，
30
，
13
，27
，
10
，
24
，得第
29
项满足条件，代 入原等差数列
427904652532
＋
584803025179(29-1)< br>＝
168
，因
584803025179*31
＝
549，得等差数列
168
＋
549
Ｎ的数都满足
这些条件．
反过来，用
168
除以素数
31
，
37
，
41
，
43
，
47
，
53
，
59
，
61
的余数必然与上面相同．
练习：
因
31
，
37
，
41
，
43
，
47
，< br>53
，
59
，
61
的最小公倍数为
549
， 当
你在
549
之内任意取一个数除以素数
31
，
37
，
41
，
43
，
47
，
53
，
59
，
61
，把余数记录下来，用同样的计算方法，必然计算出你所取的数．
你任意选择Ｎ个不同的素数，
在这Ｎ个素数乘积内任意取一个数，
除以这几
个 素数把余数记录下来，
用这里的计算方法，
必然计算出你所取的数．
这就是逆
运算．
二，复杂型
复杂型指除数中存在合数和素数，
该类题难免出现错题，
所以，
解题前必须
先进行审题．
例：Ｍ< br>/26325
余
6641
，Ｍ
/14553
余
124 19
，Ｍ
/19125
余
11141
，Ｍ
/4165
余
3746
，求Ｍ＝？
因为
,
正确的题在除数的最小公倍数内有解
,
在除数的最小公倍数 内有唯一
的解
.
而除数的最小公倍数是所含素因子最高次方的乘积
.
即
,
除数的最小公倍数
的结构为除数所含各素因子的最高次方
.
所以
,
审题与变题都要以各素因子的最
高次方为基础
.
1
，审题：
因除数：
26325
＝
3*3*3* 3*5*5*13
；
14553
＝
3*3*3*7*7*11
；19125
＝
3*3*5*5*5*17
；
4165
＝
5*7*7*17
．