※ 引述《ericpoto (Eric)》之銘言：
: 初學CRT遇到了理解方面得障礙
: 我只理解取819是因為7.9.13互質
: 而7x9x13=819，則在mod819下有解
: 接下來就完全不理解了
: 題目如下：
: X≡5 (mod7)
: X≡4 (mod9)
: X≡3 (mod13)
: 解如下：
: r1=5,r2=4,r3=3
: n1=7,n2=9,n3=13
: n=n1n2n3=819
: N1=n/n1=117
: N2=n/n2=91
: N3=n/n3=63
: M1=N1¯(mod n1)=3
: M2=N2¯(mod n2)=1
: M3=N3¯(mod n3)=6
: 取X≡r1M1N1+r2M2N2+r3M3N3 (mod 819)
: 我的問題是
: 1.為何要取N1=n/n1,是為了甚麼準備?
: 2.M1不是在(mod n1)下的N1的inverse嗎?(類推M2.M3)
: 為何可以代入(mod n1n2n3)的式子中?
: 3.為何X≡r1M1N1+r2M2N2+r3M3N3 (mod 819)
我以前也想過這個問題, 然後利用以下結果可以觀察出Chinese Remainder Theorem
是如何被建構出來的:
首先, 先解出2個聯立的結果
Given the two simultaneous equations:
x≡a1 (mod m1)
x≡a2 (mod m2)
and gcd(m1,m2)=1
Then, there is a (unique) solution and every solution has the form:
x≡a1 m2 y1+a2 m1 y2 (mod m1 m2)
, where m2 y1≡1(mod m1 ) and m1 y2≡1(mod m2 )
Proof:
∵x≡a1 (mod m1) => There is an integer u such that x=a1+u m1
x≡a2 (mod m2) => There is an integer v such that x=a2+v m2
=> a1+u m1 = a2+v m2
=> u m1 - v m2 = a2 - a1 --------(1)
∵gcd(m1,m2)=1
There exist integers s, t such that s m1 + t m2 = 1 ------- (2)
To eliminate u and v in (1),
we multiply (a2-a1) on the both sides of (2).
=> (a2-a1)s m1 + (a2-a1)t m2 = a2 - a1
Then we can take u = (a2-a1)s, v = -(a2-a1)t.
=> x = a1+u m1 = a1 + (a2-a1)s m1 = a1(1-s m1) + a2 s m1
By (2), x = a1 t m2 + a2 s m1
Then, x = a1 t m2 + a2 s m1 is a solution
Note that t m2 ≡ 1 (mod m1) and s m1 ≡ 1 (mod m2) since
the result of (2) and gcd(m1,m2)=1.
Set t = y1 s = y2 andlLet x0 = a1 t m2 + a2 s m1.
Since x0 is a solution,
x ≡ x0 (mod m1), x ≡ x0 (mod m2) or
m1 | x - x0 and m2 | x - x0
By gcd(m1, m2) = 1, m1 m2 | x - x0 => x ≡ x0 (mod m1 m2)
------------------------------------------------------------------
再來要解出n個聯立的, 就一直任取兩個化簡:
x≡a1 (mod m1)
x≡a2 (mod m2)
...
x≡a_n (mod m_n)
gcd(m_i, m_j) = 1 for i≠j
(1) 取 1 , 2式 可得
x ≡ a1 s1 m2 + a2 t1 m1 (mod m1 m2),
m2 s1 ≡ 1(mod m1), m1 t1 ≡ 1(mod m2)
(2) 取 新得到的結果和第3式
(因為gcd(m_i, m_j) = 1 => gcd(m1m2, m3) = 1, 所以直接套)
=> x ≡ (a1 s1 m2 + a2 t1 m1)s2 m3 + a3 t2 (m1 m2) ( mod (m1 m2) m3 )
≡ a1 (s1s2) m2m3 + a2 (t1s2) m1m3 + a3 t2 m1m2 ( mod m1 m2 m3)
且
s2 m3 ≡ 1(mod m1 m2)(So, s2 m3 ≡ 1 (mod m1), s2 m3 ≡ 1 (mod m2))
t2 (m1 m2) ≡ 1 (mod m3)
m2 s1 ≡ 1(mod m1), m1 t1 ≡ 1(mod m2) by (1)
=> (s1s2) m2m3 ≡ (s2 m3) (s1 m2) ≡ 1(mod m1)
(t1s2) m1m3 ≡ (t1 m1) (s2 m3) ≡ 1(mod m2)
t2 m1m2 ≡ 1 (mod m3)
....
(n-1) 剩下
x ≡ a1 s1' M1 + a2 s2' M2 + ... + a_(n-1) s_(n-1)' M_(n-1)
(mod m1m2...m_(n-1))
和
x≡a_n (mod m_n)
其中
M_k = m1m2...m_(n-1)/m_k
s_k' M_k ≡ 1 (mod m_k),
k = 1, 2, ..., n-1
由之前的規律可得知
x ≡ a1 y1 M1 + a2 y2 M2 + ... + a_n y_n M_n (mod m1m2...m_n)
M_k = m1m2...m_n/m_k
M_k y_k ≡ 1( mod m_k )
k = 1, 2, ..., n
所以Chinese Remainder Theorem 可搭配解2聯立的方法和數學歸納法得出
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.165.155