中国剩余定理

2020/9/3 五年级扛把子

孙子定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

给出n个同余式, 求满足所有式子的一个最小解,一般形式如下:

$\left\{\begin{matrix} x=a_{1}(mod \, \, m_{1}) \\ x=a_{2} (mod \, \, m_{2}) \\ .......................... \\ x=a_{n} (mod \, \, m_{n}) \end{matrix}\right.$

求解x的最小值,其中 $a_{1},a_{2} ,.....a_{n}$ , 是互质的, 如果不互质,应该用其他方法求解.

中国剩余定理给出求解公式: $x=\sum (M_{i}*c_{i}*a_{i})$

设 $M=m_{1}*m_{2}*...*m_{n}$ ,

$\left\{\begin{matrix} M_{1}=M/m_{1}\\ M_{2}=M/m_{2} \\ ......................... \\ M_{n}=M/m_{n} \end{matrix}\right.$

对于 $c_{i}$ 则构造同余式

$\left\{\begin{matrix} M_{1}*c_{1} = 1 (mod \, \, a_{1}) \\ M_{2}*c_{2} = 1 (mod \, \, a_{2}) \\ ................................. \\ M_{n}*c_{n} = 1 (mod \, \, a_{n}) \end{matrix}\right.$

其中 $M_{i}, a_{i}$ 都是已知的, 可以用exgcd求出 $c_{i}$ , 这是最主要的一步

求解方法 :https://blog.csdn.net/qq_41505957/article/details/101515687

$M_{i}, c_{i}, a_{i}$ 都已知, 可以求出x.

举个例子:

$\left\{\begin{matrix} x = 13(mod\, \, 17) \\ x = 4(mod \, \, 13) \\ x = 5(mod\, \, 7) \end{matrix}\right.$

那么

$\left\{\begin{matrix} a_{1}=13 \\ a_{2}=4 \\ a_{3}=5 \end{matrix}\right.$ $\left\{\begin{matrix} m_{1} =17\\ m_{1} =13 \\ m_{1} =7 \end{matrix}\right.$