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

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的除数还是适用的，但是对于上述两道题目，显然很难寻找对应系数，还请各位赐教！

天山草

对于我们这些非专业搞数学的人而言，重在如何解决问题，不论采用什么手段。
对于专门研究数学的人来说，就是如何求下述方程组的整数解（以第 1 道题为例）：
x=4a1=5a2+3=7a3+2=9a4=11a5+8。
我想这个也并不难吧，只是麻烦而已（具体解法见 3#楼）。
使用现成的数学软件做，很方便：
Solve[{Mod[x, 4] == 0, Mod[x, 5] == 3, Mod[x, 7] == 2, Mod[x, 9] == 0,  Mod[x, 11] == 8}, {x}, Integers]
答案是： x=13860 t +13428,
取 t = 0 得到最小解：x=13428。

也可以这样列方程（手工计算时应该这样列方程吧）：
Solve[{x == 4 a1, x == 5 a2 + 3, x == 7 a3 + 2, x == 9 a4,  x == 11 a5 + 8}, {x, a1, a2, a3, a4, a5}, Integers]
答案是：
x=13860 t +13428,
a1=3465 t+3357,
a2=2772 t+2685,
a3=1980 t+1918,
a4=1540 t+1492,
a5=1260 t+1220.
取 t = 0 得到最小解：
x=13428, a1=3357, a2=2685, a3=1918,  a4=1492,  a5=1220.

天山草

下面我试试手工计算哈。
因为 x 能被 4 和 9 整除，且 4 与 9 互质，所以 x 也能被 36 整除。
设 x = 36t1 = 5t2+3 = 7t3+2 = 11t4+8,  -------------------------------（1）  
由 36t1=5t2+3, 两边除 5 得： 7t1+t1/5=t2+3/5, 即 (t1-3)/5=t2-7t1, 此式右边是整数，所以左边 (t1-3)/5 也是整数，令 t1-3 =5u,  则 t1=3+5u, 于是 36t1=108+180u=5t2+3, 故 t2=21+36u。这样方程（1）就简化为
      x =108+180u = 7t3+2 = 11t4+8,  -------------------------------（2）
再由 7t3+2=11t4+8, 即7t3=11t4+6, 两边除7得t3=t4+(4t4+6)/7，设 4t4+6=7p, 两边除4得 t4+1=p+(3p-2)/4，令 3p-2=4k，两边除3得 p=k+(k+2)/3，令 k+2=3v，则 k=3v-2。于是p=k+(k+2)/3=(3v-2)+v=4v-2，从而t4=(7p-6)/4=(28v-14-6)/4=7v-5，t3=(11t4+6)/7=11v-7。于是有 7t3+2=11t4+8=77v-47。这样方程（2）就简化为
     x =108+180u = 77v-47,  -------------------------------------------（3）
由 108+180u = 77v-47, 两边除 77 得
    1+31/77+2u+26u/77=v-47/77，即 2+(26u+1)/77+2u=v，令 26u+1=77q，则 u+(1+q)/26=3q，令 1+q=26r，则 q=26r-1。于是
   u=(77q-1)/26=(2002r-78)/26=77r-3，v=2+(26u+1)/77+2u=180r-5。
最终求得 x =108+180u = 77v-47=36(385r-12)，令 r=1 就得到 x 的最小值为 13428.

天山草

对于主楼的第 2 题，作法是
Solve[{Mod[x, 5] == 0, Mod[x, 715] == 10, Mod[x, 247] == 140,
  Mod[x, 391] == 245, Mod[x, 187] == 109}, {x}, Integers]
解答是
x = 5311735 t + 10020。
令 t =0 得到最小解为 10020。

elim

王守恩

第2题  化简可得：
5余0，143（11*13）余10，323（17*19）余7，23余15。
10+143=153先满足143余10   满足23余15。
153+143*23=3442
3442+3289=6731
6731+3289=10020
答案10020。

第1题  小学生的方法。不一定从36开始。
解法一：从18 开始。先满足5余3，9余0
            18+5*9=63  满足11余8
            63+45*11=558
            558+495=1053
            1053+495=1548  满足4余0
            1548+495*4=3528
            3528+1980=5508
            5508+1980=7488
            7488+1980=9468
            9468+1980=11448
            11448+1980=13428
解法二：从8开始。先满足4余0，5余3，11余8。
解法三：从9开始。先满足7余2，9余0。
解法四：从16开始。先满足4余0，7余2。
解法五：从30开始。先满足7余2，11余8。
            ..........................................

解题思路：当题目给出的条件太多，不可能一下子全部满足。我们可以尝试先满足部分条件，然后慢慢向答案靠拢。

elim

对任何正整数a,b, 通过碾转相除法可得其最大公约数．
229，1109，283 那些数就是这么来的．

zikwicz

先谢谢各位的回复，我自己是学工科的，是我的外公在研究这个问题。我争取明后天把他的解法发上来，供大家参考。

elim

第二题


（1）除5余0的情况由除715余10保证，不必进一步考虑。
（2）由于除数不两两互素，这种题目未必有解，例如  除715余9，除5余4，其它题设不变就没有解。
（3）利用中国余数定理解这类题未必简捷，只是解法可以同一，比较规则机械.

zikwicz

谢谢大家的回复！

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