求“韩信点兵”的同余解法

Question

每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人，求人数最少是多少
请列出同余式，网上那些我大概看过，完全没有算理可言，并写出列出同余式后的步骤
，我的意思是不依脱那些网上的答案，因为他没有讲明为什么，请按照解同余的办法做。我一直没有想出来
回答按我的要求，我一定追加悬赏
O(∩_∩)O谢谢

Answer 1

同余方程说白了也就是个记号, 未必要用同余式变换来求解.
这个问题的一般解法就是构造性的.
解法的关键步骤是找到几个数: 910, 546, 1170, 105.
这几个数的特点是: 910是5, 7, 13的公倍数, 且mod 3余1; 546是3, 7, 13的公倍数, 且mod 5余1;
1170是3, 5, 13的公倍数, 且mod 7余1; 105是3, 5, 7的公倍数, 且mod 13余1.
如果取r = 910a+546b+1170c+105d, 则有r ≡ a (mod3), r ≡ b (mod5), r ≡ c (mod7), r ≡ d (mod13).
即r是同余方程组x ≡ a (mod3), x ≡ b (mod5), x ≡ c (mod7), x ≡ d (mod13)的一个解.
若s是该方程组的另一个解, 相减得r-s ≡ 0 (mod3), r-s ≡ 0 (mod5), r-s ≡ 0 (mod7), r-s ≡ 0 (mod13).
于是r-s被3, 5, 7, 13整除, 即被1365 = 3·5·7·13整除.
因此方程组的通解为x = r+1365k, k为任意整数.
本题将a = 1, b = 2, c = 4, d = 6代入, 得r = 7312.
当k = -5时r+1365k = 487取得最小正整数解.

下面解释一下那几个数是怎么找的.
首先这几个数存在的依据是3, 5, 7, 13两两互质.
数论里有个定理: 若m, n互质, 则存在整数u, v使得um+vn = 1.
可以看到um = 1-vn, 是m的倍数且mod n余1.
至于如何计算, 因为这道题的数还算比较小, 所以逐个验算也不困难.
还可以借助同余式稍微简化一点, 例如由3·5·13 ≡ 6 (mod 7), 只需找6的倍数使其mod 7余1.
由6·6 ≡ 1 (mod 7), 可取1170 = 6·3·5·13 ≡ 6·6 ≡ 1 (mod 7).
如果不是mod 7, 而是mod 97这样更大的数, 计算的效率还是比较低.
相对有效的办法是用辗转相除, 这里先不介绍了.
另外对于一组给定的模数, 相应的数只要计算一次, 结果能适用于不同余数的情况.

个人认为这个题一次解2个比一下解4个方程有效.
先解x ≡ 1 (mod3), x ≡ 2 (mod5). 取两个数-5和6, 得x ≡ -5·1+6·2 = 7 (mod 3·5).
再解x ≡ 7 (mod 3·5), x ≡ 4 (mod 7). 取两个数-14和15, 得x ≡ 67 (mod 3·5·7).
最后解x ≡ 67 (mod 3·5·7), x ≡ 6 (mod 13). 取两个数-104和105, 得x ≡ 487 (mod 3·5·7·13).

这里再说明一下.
由2·3-1·5 = 1, 6 = 2·3是3的倍数并mod 5余1. 由同样的等式, -5 = -1·5是5的倍数并mod 3余1.
引入负数使我们能由一个等式得到所需要的两个数. 同样的考虑在3·5·7和13时作用最明显.
由3·5·7-8·13 = 1, 105是3·5·7的倍数并mod 13余1, 而-104是13的倍数并mod 3·5·7余1.
如果非要取正整数, 那最小就是1365-104 = 1261, 计算量要大一些.

Answer 2

一个数的2倍，除以3余2，除以5余4，除以13余12，这个数正好是除以3余1，除以5余2，除以13余6
所以，（3*5*13-1）/2=97正好是除以3余1，除以5余2，除以13余6
所以，
97+3*5*13*n=97+195*n n=0,1,2,3……都是正好除以3余1，除以5余2，除以13余6
97除以7余6
195除以7余6
97+195*2除以7的余数，与6+6*2=18除以7的余数相同，18除以7余4
所以，
97+195*2=487正好是除以3余1，除以5余2，除以7余4，除以13余6
487+3*5*7*13*n=487+1365*n n=0,1,2,3……都是正好除以3余1，除以5余2，除以7余4，除以13余6
487是最小的追问

如果
我列，设有x人
x≡1（mod3)
x≡2（mod5)
x≡4（mod7)
x≡6（mod13)
这样该怎么做

追答

这真不会做

Answer 3

先计算“每3人一列余1人、5人一列余2人、7人一列余4人”
按数学家程大位诗歌算法：
三人同行七十稀，五树梅花廿一枝，
七子团圆月正半，除百零五便得知。
其值为
70×1+21×2+15×4=172=105+67
67是最小数
那么所有105乘以正数+67都符合要求
可知105÷13得8余1,67÷13得5余2
那么105每增加一倍，即增加余数1，显然增加4倍，余数即是6
那么这个数应该是105×4+67=487
不知道是不是这样追问

但是还有一个要求
13人一列余6人
不过这样下去应该很快也能求出来
为什么是这样呢，有算数理论上的依据吗

追答

上述解法就是结合了除以13余6，
（那么所有105乘以正数+67都符合要求
可知105÷13得8余1,67÷13得5余2
那么105每增加一倍，即增加余数1，显然增加4倍，余数即是6）
括弧部分即是
3、5、7的解法百度下就有

Answer 4

x≡
1（mod3)
2（mod5)
4（mod7)
6（mod13)
解:以下用==表示同余号≡.
并以向量形式描述上题,即
x==(1,2,4,6) mod (3,5,7,13)
先求得
x1==(1,0,0,0) mod (3,5,7,13)
x2==(0,1,0,0) mod (3,5,7,13)
x3==(0,0,1,0) mod (3,5,7,13)
x4==(0,0,0,1) mod (3,5,7,13)
再进行线性叠加,即得解:
x=x1+2x2+4x3+6x4. mod lcm(3,5,7,13)
此处lcm表示最小公倍数,也用中括号代替,记成[3,5,7,13]
对于两两互质的数,其lcm就是它们的积.
注:
1:我们可以看到,完全可以用矩阵论\线性代数理论来处理同余问题;
2:x1,x2,x3,x4并列,构成单位矩阵;
3:x可以表示成两个向量的内积(点积,标积,数量积), 即x=(1,2,4,6)·(x1,x2,x3,x4)
4: 以上就是中国剩余定理的本质性描述.插值法中的拉格朗日插值,也是这样的原理.
5:这种方案,x1,x2,x3,x4的计算是同步并行的.
6:类以牛顿插值,还可以使用以下过程:
x1=(1,1,1,1) mod (3,5,7,13)
x2=(0,1,1,1) mod (3,5,7,13)
x3=(0,0,2,2) mod (3,5,7,13)
x4=(0,0,0,2) mod (3,5,7,13)
再取x=x1+x2+x3+x4.
也就是:
x1=1
x2=(0,1) mod (3, (5,7,13))
x3=(0,2) mod ((3,5), {7,13))
x4==(0,2) mod ((3,5,7), 13)
其矩阵形式是一个上三角矩阵.
7: 中国剩余定理使用了单位向量.事实上,为便于计算,可以不必使用单位向量.
过程如下:
x1==(1,0,0,0) mod (3,5,7,13)
x2==(0,2,0,0) mod (3,5,7,13)
x3==(0,0,4,0) mod (3,5,7,13)
x4==(0,0,0,6) mod (3,5,7,13)
再取x=x1+x2+x3+x4.
在下面的过程中,会看到此种方式对计算的简化.因此,这是对中国剩余定理的计算过程的一种简单的改进,也有助于我们打破对中国剩余定理的迷信,进一步认识到其本质.
8:洪伯阳同余表示:
ax==b mod m, 记成 x=b/a mod m
并且,可以将 b/a作为带分数处理; 可以将b/a 同时乘除一个与m 互质的数而保持同解; 可以将b,a替换为它关于模m的同余类中的任一个等价元.即b'==b mod m, 可以用b'取代b而同余式保持同解.
可以在上式用使用比例的性质.
9: 为直观,我常用|||取代同余号mod.
x==
1 ||| 3
2 ||| 5
4 ||| 7
6 ||| 13
基于注释7和8, 同余式的解可以如下表示,
==
{$$$
(5*7*13) * [1/(5*7*13) mod 3]+
(3*7*13) * [ 2/(3*7*13) mod 5]+
(3*5*13) * [4/(3*5*13) mod 7]+
(3*5*7) * [ 6/(3*5*7) mod 13]
$$$}
==进而,对上面的过程,我有以下的简化改进记法,称为模积表示法,用以解同余式.
1/(5*7*13) @ 3
2/(3*7*13) @ 5
4/(3*5*13) @ 7
6/(3*5*7) @ 13
==(开始使用洪伯阳表示的性质,并将乘号改动为逗号简化书写,改为逗号不是必须的,我在草稿纸常这样写 )
1/(-1,1,1) @ 3
2/(21==1,-2) @5
4/(15==1,13==-1)@7
6/(105==1) @13
==
-1 @ 3
-1 @5
-4 @7
6 @ 13
==
[注意体会模积表示; 注意上面各式是对称的,位置与计算次序可以任意;注意任一行,@符号前的内容可以关于@后的模取代为同余类的任意等价元]
-8==
7 @15
-4 @ 7
6 @ 13
==
49-60 @ 15*7==
-11 @ 105
6 @ 13
==630-143 MOD 13*105
== 487 mod 1365
以上过程,在了解了中国剩余定理的本质和改进方案.熟悉了洪伯阳表示及何冬州模积表示之后,
能结合心算或简化中间过程,快速计算出同余式组的解.
注意到各式的对称性,即无先后之分,用多种过程来计算与验证,曾经是我在2005年初发现这种方法时的一种乐趣.
利用洪伯阳表示的性质,进行笔算求幂余和解大模的同余式,也很方便.
这种过程我曾考虑过自动编程方案,仍在思考之中.
外一则:
对于同余号 mod m, 可以认为它与一个可平移到等式两端任意同阶的项上的一个代数和项: ±mk.
以此破除对同余概念的迷惑.同余式与不定方程式是完全等效的.
相关内容, 请搜索:
wsktuuytyh 同余新概念
关于一次不定方程的简化解法,请搜索
不定方程解法 wsktuuytyh本回答被提问者和网友采纳