# 中国剩余定理详解

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) \$\$

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

\$\$/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)\$\$

\$\$/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}\$\$

\$\$/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}\$\$

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

## 例题

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