数学-数论-中国剩余定理

Posted by

定义

给出一个线性同余方程组:\(\begin{cases}x\equiv a_1\quad(mod\ m_1)\\x\equiv a_2\quad(mod\ m_2)\\ \ldots \\x\equiv a_n\quad(mod\ m_n)\end{cases}\),其中\(m_i\)两两互质,中国剩余定理用于求这样的方程组的解。

求解算法

思路与简单证明

将每一个方程分开讨论:
\[\begin{cases}x_i\equiv a_i\quad(mod\ m_i)\end{cases},\quad 1\leq i\leq n\]
对于每一个方程,\(x_i\)应该满足\(x_i\equiv a_i\quad(mod\ m_i)\);
考虑其他方程,令\(x=\sum x_i\),为了满足原来线性方程组的条件,可以简单地认为需要满足\(\sum x_j\equiv a_i\quad(mod\ m_i),\quad j\not=i\);
于是每个\(x_i\)又需要满足\(\forall m_j(j\not=i),x_i\ mod\ m_j=0\)。
于是可以简单地认为\(x_i\ mod\ \prod_{j\not=i} m_j=0\)。
设\(k=\prod_{j\not=i}m_j,n=tk\),于是\(tk\equiv a_i\quad(mod\ m_i)\),移项得\(t\equiv a_i\cdot k^{-1}\quad(mod\ m_i)\)。
得出\(x_i=a_i\cdot k^{-1}\cdot k\),为了得出最小解,\(x=\sum (a_i\cdot k^{-1}\cdot k)\ mod\ \sum m_i\),注意这里\(k^{-1}\)是指\(k\)在模\(m_i\)意义下的逆元,不能简单地消去。

扩展

思路与简单证明

当\(m_i\)不满足两两互质时,考虑两两合并:
对于两个方程:
\[x\equiv a_1\quad(mod\ m_1)\\
x\equiv a_2\quad(mod\ m_2)\]
等式形式:
\[x=a_1k_1+m_1\\
x=a_2k_2+m_2\]
合并起来,移项:
\[a_1k_1+a_2k_2=m_2-m_1\]
用扩展欧几里得解该方程(注意无解情况),得出解\(k_1\),那么x的一个特解就是\(a_1k_1+m_1\),为了保证\(x\)满足原来两个方程,x的通解可以表示成\(a_1k_1+m_1+k\cdot lcm(m_1,m-2)\),于是得出新的同余方程:
\[x\equiv a_1k_1+m_1\quad(mod\ lcm(m_1,m-2))\]

实现

One comment

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注