锐客网

  1. 首页 > 睿知 > it技术 > >

线性代数|中国剩余定理（CRT）

算法线性代数

问题引出 “有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。——百度百科
前置知识 同余的性质
解题思路 Tip：建议读者不要太着急后翻，按照顺序阅读有助于理解
依题意可得：
{ x ≡ 2 ( m o d3 ) x ≡ 3 ( m o d5 ) x ≡ 2 ( m o d7 ) \left\{\begin{matrix}x\equiv 2(mod\ 3)\\x\equiv 3(mod\ 5)\\x\equiv 2(mod\ 7)\end{matrix}\right. ????x≡2(mod 3)x≡3(mod 5)x≡2(mod 7)?
【线性代数|中国剩余定理（CRT）】要求求出x x x 。三个方程式放在一起不好想，先拆开，变成三条方程：
x 1 ≡ 2 ( m o d3 ) x 2 ≡ 3 ( m o d5 ) x 3 ≡ 2 ( m o d7 ) x_1\equiv 2(mod\ 3)\\x_2\equiv 3(mod\ 5)\\x_3\equiv 2(mod\ 7) x1?≡2(mod 3)x2?≡3(mod 5)x3?≡2(mod 7)
现在，假设：
x 1 + x 2 ≡ 2 ( m o d3 ) , x 1 + x 3 ≡ 2 ( m o d3 ) x_1+x_2\equiv 2(mod\ 3),x_1+x_3\equiv 2(mod\ 3) x1?+x2?≡2(mod 3),x1?+x3?≡2(mod 3)
x 2 + x 1 ≡ 3 ( m o d5 ) , x 2 + x 3 ≡ 3 ( m o d5 ) x_2+x_1\equiv 3(mod\ 5),x_2+x_3\equiv 3(mod\ 5) x2?+x1?≡3(mod 5),x2?+x3?≡3(mod 5)
x 3 + x 1 ≡ 2 ( m o d7 ) , x 3 + x 2 ≡ 2 ( m o d7 ) x_3+x_1\equiv 2(mod\ 7),x_3+x_2\equiv 2(mod\ 7) x3?+x1?≡2(mod 7),x3?+x2?≡2(mod 7)
那么：
∵ x 1 ≡ x 1 + 0 ≡ x 1 + x 2 ≡ x 1 + x 3 ≡ 2 ( m o d3 ) \because x_1\equiv x_1+0\equiv x_1+x_2\equiv x_1+x_3\equiv2(mod\ 3) ∵x1?≡x1?+0≡x1?+x2?≡x1?+x3?≡2(mod 3)
∴ x 2 ≡ x 3 ≡ 0 ( m o d3 ) \therefore x_2\equiv x_3\equiv 0(mod\ 3) ∴x2?≡x3?≡0(mod 3)
∴ 3 ∣ x 2 , 3 ∣ x 3 \therefore 3|x_2,3|x_3 ∴3∣x2?,3∣x3?
∵ x 2 ≡ x 2 + 0 ≡ x 2 + x 1 ≡ x 2 + x 3 ≡ 3 ( m o d5 ) \because x_2\equiv x_2+0\equiv x_2+x_1\equiv x_2+x_3\equiv3(mod\ 5) ∵x2?≡x2?+0≡x2?+x1?≡x2?+x3?≡3(mod 5)
∴ x 1 ≡ x 3 ≡ 0 ( m o d5 ) \therefore x_1\equiv x_3\equiv 0(mod\ 5) ∴x1?≡x3?≡0(mod 5)
∴ 5 ∣ x 1 , 5 ∣ x 3 \therefore 5|x_1,5|x_3 ∴5∣x1?,5∣x3?
∵ x 3 ≡ x 3 + 0 ≡ x 3 + x 1 ≡ x 3 + x 2 ≡ 2 ( m o d7 ) \because x_3\equiv x_3+0\equiv x_3+x_1\equiv x_3+x_2\equiv2(mod\ 7) ∵x3?≡x3?+0≡x3?+x1?≡x3?+x2?≡2(mod 7)
∴ x 1 ≡ x 2 ≡ 0 ( m o d7 ) \therefore x_1\equiv x_2\equiv 0(mod\ 7) ∴x1?≡x2?≡0(mod 7)
∴ 7 ∣ x 1 , 7 ∣ x 2 \therefore 7|x_1,7|x_2 ∴7∣x1?,7∣x2?
我们发现，如果这样假设，那么x 1 + x 2 + x 3 x_1+x_2+x_3 x1?+x2?+x3? 就会是方程的一个解：
∵ x 2 ≡ x 3 ≡ 0 ( m o d3 ) \because x_2\equiv x_3\equiv 0(mod\ 3) ∵x2?≡x3?≡0(mod 3)
∴ x 1 + x 2 + x 3 ≡ x 1 ≡ 2 ( m o d3 ) \therefore x_1+x_2+x_3\equiv x_1\equiv2(mod\ 3) ∴x1?+x2?+x3?≡x1?≡2(mod 3)
∵ x 1 ≡ x 3 ≡ 0 ( m o d5 ) \because x_1\equiv x_3\equiv 0(mod\ 5) ∵x1?≡x3?≡0(mod 5)
∴ x 1 + x 2 + x 3 ≡ x 2 ≡ 3 ( m o d5 ) \therefore x_1+x_2+x_3\equiv x_2\equiv3(mod\ 5) ∴x1?+x2?+x3?≡x2?≡3(mod 5)
∵ x 1 ≡ x 2 ≡ 0 ( m o d7 ) \because x_1\equiv x_2\equiv 0(mod\ 7) ∵x1?≡x2?≡0(mod 7)
∴ x 1 + x 2 + x 3 ≡ x 3 ≡ 2 ( m o d7 ) \therefore x_1+x_2+x_3\equiv x_3\equiv2(mod\ 7) ∴x1?+x2?+x3?≡x3?≡2(mod 7)
满足题意，那么现在就只需要找出求解x 1 , x 2 , x 3 x_1,x_2,x_3 x1?,x2?,x3? 的方法。设x 1 = 5 × 7 × k 1 = 35 k 1 , x 2 = 3 × 7 × k 2 = 21 k 2 , x 3 = 3 × 5 × k 3 = 15 k 3 x_1=5\times 7\times k_1=35k_1,x_2=3\times 7\times k_2=21k_2,x_3=3\times 5\times k_3=15k_3 x1?=5×7×k1?=35k1?,x2?=3×7×k2?=21k2?,x3?=3×5×k3?=15k3?。将它们分别代入三个式子中：
35 k 1 ≡ 2 ( m o d3 ) 35k_1\equiv 2(mod\ 3) 35k1?≡2(mod 3)
21 k 2 ≡ 3 ( m o d5 ) 21k_2\equiv 3(mod\ 5) 21k2?≡3(mod 5)
15 k 3 ≡ 2 ( m o d7 ) 15k_3\equiv 2(mod\ 7) 15k3?≡2(mod 7)
右边统一化一：
35 k 1 × 1 2 ≡ 1 ( m o d3 ) 35k_1\times\frac{1}{2}\equiv 1(mod\ 3) 35k1?×21?≡1(mod 3)
21 k 2 × 1 3 ≡ 1 ( m o d5 ) 21k_2\times\frac{1}{3}\equiv 1(mod\ 5) 21k2?×31?≡1(mod 5)
15 k 3 × 1 2 ≡ 1 ( m o d7 ) 15k_3\times\frac{1}{2}\equiv 1(mod\ 7) 15k3?×21?≡1(mod 7)
k 1 × 35 2 ≡ 1 ( m o d3 ) k_1\times \frac{35}{2}\equiv 1(mod\ 3) k1?×235?≡1(mod 3)
k 2 × 21 3 ≡ 1 ( m o d5 ) k_2\times \frac{21}{3}\equiv 1(mod\ 5) k2?×321?≡1(mod 5)
k 3 × 15 2 ≡ 1 ( m o d7 ) k_3\times \frac{15}{2}\equiv 1(mod\ 7) k3?×215?≡1(mod 7)
分别求出k 1 , k 2 , k 3 k_1,k_2,k_3 k1?,k2?,k3? 在对应模数意义下的值，再通过它们的值，求出x 1 , x 2 , x 3 x_1,x_2,x_3 x1?,x2?,x3? ，相加，并且m o d3 × 5 × 7 mod\ 3\times5\times7 mod 3×5×7得到它的解在m o d105 mod\ 105 mod 105 意义下，是23 23 23。
尝试将特殊情况一般化：
假 设 m 中 的 数 两 两 互 质 假设m中的数两两互质 假设m中的数两两互质
{ x ≡ a 1 ( m o dm 1 ) x ≡ a 2 ( m o dm 2 ) . . . . . . x ≡ a n ( m o dm n ) \left\{\begin{matrix}x\equiv a_1(mod\ m_1)\\x\equiv a_2(mod\ m_2)\\......\\x\equiv a_n(mod\ m_n)\end{matrix}\right. ????????x≡a1?(mod m1?)x≡a2?(mod m2?)......x≡an?(mod mn?)?
假 设 对 于 任 意 的i( 1 ≤ i ≤ n )都 有 ∏ j = 1 n m j m i ∣ x i , 则 对 于 任 意 的i( 1 ≤ i ≤ n )都 有 x i = k i × ∏ j = 1 n m j m i 假设对于任意的\ i\ (1\le i\le n)\ 都有\frac{\prod\limits_{j=1}^nm_j}{m_i}|x_i,则对于任意的\ i\ (1\le i\le n)\ 都有x_i=k_i\times\frac{\prod\limits_{j=1}^nm_j}{m_i} 假设对于任意的 i (1≤i≤n) 都有mi?j=1∏n?mj??∣xi?,则对于任意的 i (1≤i≤n) 都有xi?=ki?×mi?j=1∏n?mj??
再 令 M i = ∏ j = 1 n m j m i , 带 入 原 式 得 ： 再令M_i=\frac{\prod\limits_{j=1}^nm_j}{m_i},带入原式得： 再令Mi?=mi?j=1∏n?mj??,带入原式得：
{ k 1 × M 1 ≡ a 1 ( m o dm 1 ) k 2 × M 2 ≡ a 2 ( m o dm 2 ) . . . . . . k n × M 3 ≡ a n ( m o dm n ) \left\{\begin{matrix}k_1\times M_1\equiv a_1(mod\ m_1)\\k_2\times M_2\equiv a_2(mod\ m_2)\\......\\k_n\times M_3\equiv a_n(mod\ m_n)\end{matrix}\right. ????????k1?×M1?≡a1?(mod m1?)k2?×M2?≡a2?(mod m2?)......kn?×M3?≡an?(mod mn?)?
将 右 边 化 一 ： 将右边化一： 将右边化一：
{ k 1 × M 1 × 1 a 1 ≡ 1 ( m o dm 1 ) k 2 × M 2 × 1 a 2 ≡ 1 ( m o dm 2 ) . . . . . . k n × M n × 1 a n ≡ 1 ( m o dm n ) \left\{\begin{matrix}k_1\times M_1\times\frac{1}{a_1}\equiv 1(mod\ m_1)\\k_2\times M_2\times\frac{1}{a_2}\equiv 1(mod\ m_2)\\......\\k_n\times M_n\times\frac{1}{a_n}\equiv 1(mod\ m_n)\end{matrix}\right. ????????k1?×M1?×a1?1?≡1(mod m1?)k2?×M2?×a2?1?≡1(mod m2?)......kn?×Mn?×an?1?≡1(mod mn?)?
表 示 出 k ： 表示出k： 表示出k：
{ k 1 ≡ 1 M 1 × 1 a 1 ( m o dm 1 ) k 2 ≡ 1 M 2 × 1 a 2 ( m o dm 2 ) . . . . . . k n ≡ 1 M n × 1 a n ( m o dm n ) \left\{\begin{matrix}k_1\equiv \frac{1}{M_1\times\frac{1}{a_1}}(mod\ m_1)\\k_2\equiv \frac{1}{M_2\times\frac{1}{a_2}}(mod\ m_2)\\......\\k_n\equiv \frac{1}{M_n\times\frac{1}{a_n}}(mod\ m_n)\end{matrix}\right. ????????????k1?≡M1?×a1?1?1?(mod m1?)k2?≡M2?×a2?1?1?(mod m2?)......kn?≡Mn?×an?1?1?(mod mn?)?
化 简 ： 化简： 化简：
{ k 1 ≡ 1 M 1 × 1 1 a 1 ≡ 1 M 1 × a 1 ( m o dm 1 ) k 2 ≡ 1 M 2 × 1 1 a 2 ≡ 1 M 2 × a 2 ( m o dm 2 ) . . . . . . k n ≡ 1 M n × 1 1 a n ≡ 1 M n × a n ( m o dm n ) \left\{\begin{matrix}k_1\equiv \frac{1}{M_1}\times\frac{1}{\frac{1}{a_1}}\equiv\frac{1}{M_1}\times a_1(mod\ m_1)\\k_2\equiv \frac{1}{M_2}\times\frac{1}{\frac{1}{a_2}}\equiv\frac{1}{M_2}\times a_2(mod\ m_2)\\......\\k_n\equiv \frac{1}{M_n}\times\frac{1}{\frac{1}{a_n}}\equiv\frac{1}{M_n}\times a_n(mod\ m_n)\end{matrix}\right. ????????????k1?≡M1?1?×a1?1?1?≡M1?1?×a1?(mod m1?)k2?≡M2?1?×a2?1?1?≡M2?1?×a2?(mod m2?)......kn?≡Mn?1?×an?1?1?≡Mn?1?×an?(mod mn?)?
最 终 答 案 ： x ≡ ∑ i = 1 n k i × M i ( m o d∏ i = 1 n m i ) \boxed{最终答案：x\equiv\sum\limits_{i=1}^nk_i\times M_i(mod\ \prod\limits_{i=1}^nm_i)} 最终答案：x≡i=1∑n?ki?×Mi?(mod i=1∏n?mi?)?

    推荐阅读


    上一篇：数据结构与算法|[No000060]冷读热读（读书九问）

    下一篇：宅家半个月，我总结出读万卷书的|宅家半个月，我总结出读万卷书的 7 大方法