请教大家 一次同余式组的解法

zikwicz

向各位学者请教一次同余式组的解法。有以下两道题目，想向大家请教一下怎么求解（用数学的方法）呢？谢谢！！！


（1）求11除余8， 5除余3，9除余0，4除余0，7除余2的数。

（2）古人黄宗宪著的“求一术通解”原文如下：
“今有数不知总，以五累减之无剩，以七百十五累减之剩十，以二百四十七累减之剩一百四十，以三百九十一累减之剩二百四十五，以一百八十七累减之剩一百零九，问总数若干。”
即：求5除余0，715除余10，247除余140，391除余245，187除余109的数。

我们都知道孙子剩余定理，《孙子算经》中“物不知数”问题说：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”即被三除余二，被五除余三，被七除余二的最小整数。这个问题称作孙子问题，俗称韩信点兵。中国把解法编成四句歌诀：“三人同行七十稀，五树梅花廿一只，七子团圆正半月，除百零五便得知。”即2×70+3×21+2×15-2×105=23。

这个方法对于简单的3,5,7的除数还是适用的，但是对于上述两道题目，显然很难寻找对应系数，还请各位赐教！

aimisiyou

$$显然此数X加上12后为4、5、7的倍数，即X=4*5*7*K1-12=140*K1-12；$$
$$又因为X为9的倍数，所以X=140*6*K2-12=840*K2-12；$$
$$又因为X除以11余8，所以X=840*25*K3-12=21000*K3-12$$

kastin

请搜索“中国剩余定理”。

kastin

(1) 因为模两两互质，故直接应用孙子定理（中国剩余定理），解为 `x\equiv 13428 \pmod{13860}`

中国剩余定理算法

(2) 模进行质因数分解，于是问题可等价为 5除余0，5除余10，11除余10，13除余10，13除余140，19除余140，17除余245，23除余245，11除余109，17除余109。进一步化简为
5除余0，11除余10，13除余10，19除余7，17除余7，23除余15。
现在模两两互质了，直接利用上面的公式可得 `x\equiv 10020 \pmod{5311735}`

mathematica

1. ChineseRemainder[{8, 3, 0, 0, 2}, {11, 5, 9, 4, 7}]

复制代码

得到答案
13428

1. LCM @@ {11, 5, 9, 4, 7}

复制代码

13860
因此是
13860k+13428的所有正整数,
这个题很弱智,是吗?

mathematica

In[6]:= ChineseRemainder[{0, 10, 140, 245, 109}, {5, 715, 247, 391,
  187}]

Out[6]= 10020

In[7]:= LCM @@ {5, 715, 247, 391, 187}

Out[7]= 5311735

mathematica

告诉你一个笨办法,穷举法!
先求最小公倍数,记为N
从零开始,一个一个地试!一共实验N次,
然后所有满足的都是解,如果不满足就没有解!

这办法虽然很笨,但是确实很有效的办法

zikwicz

谢谢大家的回复！

首先，我们讨论的是用数学的方法，不借助计算机程序来求解；其次，对于以上两题，我也有一种解法。其中，第一题如果考虑求最小正整数解，则考虑余数变化时有13860道题，对于这一题，可以给大家提供一种心算的方法，一分钟之内可以算出答案。我会尽快上传一下，供大家参考！

zikwicz

附上第一题的心算解法。

zikwicz

https://pan.baidu.com/s/1kVnscJX

这里只能上传256K以内的文件。。。只能放到网盘了