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*M1 + R2*N2*M2 + R3*N3*M3 + R4*N4*M4 (mod Z)

Rn 是餘數
R1 = 2

R2 = 1
R3 = 5

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


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

大衍求一
N1 * M1 = 55 * M1 ≡ 1 (3)
N2 * M2 = 33 * M2 ≡ 1 (5)
N3 * M3 = 15 * M3 ≡ 1 (11)
得
M1 = 1
M2 = 2
M3 = 3

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

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

沒有留言:

張貼留言