中国剩余定理详解

2018-02-07 11:32:58来源:cnblogs.com作者:自为风月马前卒人点击

分享

引入

我国古代数学著作《孙子算经》中有一道题目,它的描述是这样的

今有物不知其数,三三数之余二;五五数之余三;七七数之余二。问物几何?

这道题用现代数学理论来看,无非就是解一个方程

/begin{cases}x/equiv 2/left( mod/ 3/right) //
x/equiv 3/left( mod/ 5/right) //
x/equiv 2/left( mod/ 7/right) /end{cases}

那么这个方程怎么解呢?

这需要用到我们祖先的伟大创造——中国剩余定理

中国剩余定理

在很久以前,数学领域还没有像扩展欧几里得这种东西。对于这个问题,我们祖先采用了构造的方法

构造过程如下

首先考虑三个特殊方程

/begin{cases}x/equiv 1/left( mod/ 3/right) //
x/equiv 0/left( mod/ 5/right) //
x/equiv 0/left( mod/ 7/right) /end{cases}

/begin{cases}x/equiv 0/left( mod/ 3/right) //
x/equiv 1/left( mod/ 5/right) //
x/equiv 0/left( mod/ 7/right) /end{cases}

/begin{cases}x/equiv 0/left( mod/ 3/right) //
x/equiv 0/left( mod/ 5/right) //
x/equiv 1/left( mod/ 7/right) /end{cases}

他们的特殊解

那第一个方程来说,它实际上等同于解一个同余式

 $$35y/equiv 1/left( mod/ 3/right) $$

因为$x$一定是$5*7=35$的倍数

化简一下当面的式子

$$2y/equiv 1/left( mod/ 3/right) $$

我们不难得出解$y=2$,此时$x=70$

同理,对于第二第三个式子我们可以运用相同的方法求解

$$/begin{pmatrix} 1 // 0 // 0 /end{pmatrix}=70/begin{pmatrix} 0 // 1 // 0 /end{pmatrix}=21/begin{pmatrix} 0 // 0 // 1 /end{pmatrix}=15$$

那么最终的答案为

$$/begin{pmatrix} 2 // 3 // 2 /end{pmatrix}=2/begin{pmatrix} 1 // 0 // 0 /end{pmatrix}+3/begin{pmatrix} 0 // 1 // 0 /end{pmatrix}+2/begin{pmatrix} 0 // 0 // 1 /end{pmatrix}$$

$$=2/times 70+3/times 21+2/times 15/equiv 23/left( mod/ 105/right)$$

我们这样就可以求出解了。

但是这仅仅是三个式子的情况,如果推广到$r$个呢?

其实是一样的,都是利用构造的手段。

下面我们来推广一下。

设有$r$个同余式,其中$m_i$两两互素,注意$m$必须两两互素,否则答案错误。其实不互素也可以搞不过要用更神奇的东西

设$N=/prod ^{r}_{i=1}m_{i}$

对于同余方程组

$$/begin{cases}x/equiv b_{1}/left( mod/ m_{1}/right) // x/equiv b_{2}/left( mod/ m_{2}/right) // /ldots // x/equiv br/left( mod/ m_r/right) /end{cases}$$

在模$N$同余的意义下有唯一解

这个方程怎么解呢?

我们仍然像前面一样,考虑构造

$$/begin{cases}x/equiv 0/left( mod/ m_{1}/right) // /ldots // x/equiv 0/left( mod/ m_{i-1}/right) // /ldots // x/equiv 1/left( mod/ m_{i}/right) // /ldots // x/equiv 0/left( mod/ m_{i+1}/right) // /ldots // x/equiv0/left( mod/ M_{r}/right) /end{cases}$$

像上面那样,我们令$x=(N/m_i)*y$

那么我们现在需要解出

$/left( N/m_{i}/right) y/equiv 1/left( mod/ m_{i}/right) $

这个东西怎么搞呢?

聪明的你肯定已经知道啦,这不就是个逆元嘛,想怎么搞就怎么搞

如果你不知道怎么搞的话可以看这里

那么方程的解为$x_{0}=b_{1}x_{1}+b_{2}x_{2}+/ldots +b_{r}x_{r}/left( mod/ N/right)$

怎么样?似不似很简单?

例题

有了上面的知识代码应该不难写

放一道水题

http://poj.org/problem?id=1006

题解(很久之前做的)

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台