2014年7月13日 星期日

中國餘式定理 (Chinese remainder theorem)

http://4rdp.blogspot.com/2014/07/chinese-remainder-theorem.html

橘子多少個一文,網友行天下提到中國餘式定理一詞,其實就是現代版的大衍求一術,以代數式來求解,今補充內容。

前文所舉的例子,
X ≡ 2 (3)     ‧‧‧ X 除 3 餘 2
X ≡ 1 (5)     ‧‧‧ X 除 5 餘 1
X ≡ 5 (11)   ‧‧‧ X 除 11 餘 5

其實我們要解的代數式如下:
X = R1*N1*M+ R2*N2*M+ R3*N3*M+ R4*N4*M4 (mod Z)

R是餘數
R= 2

R= 1
R= 5

Z   是所有除數的乘積
Z = 3*5*11 = 165


N是自己除外,其餘除數的乘積
N= 5*11 = 55
N= 3*11 = 33
N= 3*5 = 15

大衍求一
NM1 = 55 M1 ≡ 1 (3)
NM2 = 33 M2 ≡ 1 (5)
NM3 = 15 M3 ≡ 1 (11)

M= 1
M= 2
M= 3

X = R1*N1*M+ R2*N2*M+ R3*N3*M+ R4*N4*M4 (mod Z)
   = 2*55*1 + 1*33*2 + 5*15*3 (mod 165)
   = 401 (mod 165)
   = 71

各位就套公式算看看橘子應該有多少個?

沒有留言:

張貼留言