投稿 资料上传 搜索
您现在的位置是: 首页 > 文章 > 正文

中国剩余定理

孙子定理是中国古代求解一次同余式组的方法。是数论中一个重要定理。一元线性同余方程组问题最早可见于中国南北朝时期(公元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.

M = 17*13*7=1547 ,求出M_{i}

\left\{\begin{matrix} M_{1}=91 \\ M_{2}=119 \\ M_{3}=221 \end{matrix}\right.

构造同余方程

\left\{\begin{matrix} 91*c_{1} =1(mod\, \,17 )\\ 119*c_{2} =1(mod\, \,13 ) \\ 221*c_{3} =1(mod\, \,7 ) \end{matrix}\right.

用扩展欧几里得解得

\left\{\begin{matrix} c_{1}=3 \\ c_{2}=-6 \\ c_{3}=2 \end{matrix}\right.

x=13*91*3 + 4*119*(-6) + 5*221*2 = 2903

转载于:

文章标签:
阿里云服务器采购季
给作者打赏,鼓励TA抓紧创作!
评论