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表示最小公倍數(shù),也用中括號代替,記成[3,5,7,13]
對于兩兩互質(zhì)的數(shù),其lcm就是它們的積.
注:
1:我們可以看到,完全可以用矩陣論\線性代數(shù)理論來處理同余問題;
2:x1,x2,x3,x4并列,構(gòu)成單位矩陣;
3:x可以表示成兩個向量的內(nèi)積(點積,標積,數(shù)量積), 即x=(1,2,4,6)·(x1,x2,x3,x4)
4: 以上就是中國剩余定理的本質(zhì)性描述.插值法中的拉格朗日插值,也是這樣的原理.
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.
在下面的過程中,會看到此種方式對計算的簡化.因此,這是對中國剩余定理的計算過程的一種簡單的改進,也有助于我們打破對中國剩余定理的迷信,進一步認識到其本質(zhì).
8:洪伯陽同余表示:
ax==b mod m, 記成 x=b/a mod m
并且,可以將 b/a作為帶分數(shù)處理; 可以將b/a 同時乘除一個與m 互質(zhì)的數(shù)而保持同解; 可以將b,a替換為它關(guān)于模m的同余類中的任一個等價元.即b'==b mod m, 可以用b'取代b而同余式保持同解.
可以在上式用使用比例的性質(zhì).
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) mod7]+
(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
==(開始使用洪伯陽表示的性質(zhì),并將乘號改動為逗號簡化書寫,改為逗號不是必須的,我在草稿紙常這樣寫 )
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
==
[注意體會模積表示; 注意上面各式是對稱的,位置與計算次序可以任意;注意任一行,@符號前的內(nèi)容可以關(guān)于@后的模取代為同余類的任意等價元]
-8==
7@15
-4 @ 7
6 @ 13
==
49-60 @ 15*7==
-11 @ 105
6 @ 13
==630-143 MOD 13*105
== 487 mod 1365
以上過程,在了解了中國剩余定理的本質(zhì)和改進方案.熟悉了洪伯陽表示及何冬州模積表示之后,
能結(jié)合心算或簡化中間過程,快速計算出同余式組的解.
注意到各式的對稱性,即無先后之分,用多種過程來計算與驗證,曾經(jīng)是我在2005年初發(fā)現(xiàn)這種方法時的一種樂趣.
利用洪伯陽表示的性質(zhì),進行筆算求冪余和解大模的同余式,也很方便.
這種過程我曾考慮過自動編程方案,仍在思考之中.
外一則:
對于同余號 mod m, 可以認為它與一個可平移到等式兩端任意同階的項上的一個代數(shù)和項: ±m(xù)k.
以此破除對同余概念的迷惑.同余式與不定方程式是完全等效的.
相關(guān)內(nèi)容, 請搜索:
wsktuuytyh同余新概念
關(guān)于一次不定方程的簡化解法,請搜索
不定方程解法 wsktuuytyh