题目

求“韩信点兵”的同余解法
每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人,求人数最少是多少
请列出同余式,网上那些我大概看过,完全没有算理可言,并写出列出同余式后的步骤
,我的意思是不依脱那些网上的答案,因为他没有讲明为什么,请按照解同余的办法做.我一直没有想出来
回答按我的要求,

提问时间：2021-03-16

答案

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