# 中國剩餘定理

(由孫子定理跳轉過嚟)

${\displaystyle {\begin{cases}x\equiv 2\mod 3\\x\equiv 3\mod 5\\x\equiv 2\mod 7\end{cases}}}$

## 孫子定理

${\displaystyle a,b\in \mathbb {Z} }$ 同埋${\displaystyle m,n\in \mathbb {N} }$

${\displaystyle a_{1},a_{2},\cdots ,a_{n}\in \mathbb {Z} }$ 同埋${\displaystyle b_{1},b_{2},\cdots ,b_{n}\in \mathbb {Z} }$

## 求解

${\displaystyle (1)}$ 得知${\displaystyle x-a|m}$ ，即係有一個${\displaystyle p\in \mathbb {Z} }$ 符合${\displaystyle mp=(x-a)}$

${\displaystyle x=mp-a}$ ${\displaystyle (2)}$ 得知${\displaystyle mp-a\equiv b\mod n}$

{\displaystyle {\begin{aligned}mp-a&\equiv b&\mod n\\mp&\equiv a+b&\mod n\\\end{aligned}}}

${\displaystyle mc+nd=1}$ 可以推出${\displaystyle nd=1-mc}$ ${\displaystyle n|1-mc}$ ${\displaystyle mc\equiv 1\mod n}$

{\displaystyle {\begin{aligned}mp&\equiv a+b&\mod n\\(cm)p&\equiv c(a+b)&\mod n\\p&\equiv c(a+b)&\mod n\end{aligned}}}

## 例子

${\displaystyle {\begin{cases}x\equiv 2\mod 3\\x\equiv 3\mod 11\\x\equiv 2\mod 7\end{cases}}}$

${\displaystyle x\equiv 2\mod 3}$ 得知，有一個整數${\displaystyle m\in \mathbb {Z} }$ 符合${\displaystyle 3m=x-2}$

${\displaystyle x=3m+2}$ ${\displaystyle x\equiv 3\mod 11}$ ，得出${\displaystyle 3m+2\equiv 3\mod 11}$

{\displaystyle {\begin{aligned}3m+2&\equiv 3\mod 11\\3m&\equiv 1\mod 11\\\end{aligned}}}

{\displaystyle {\begin{aligned}11&=3\times 3+2\\3&=2\times 1+1\\\end{aligned}}}

{\displaystyle {\begin{aligned}1&=3-2\times 1\\&=3-(11-3\times 3)\\&=3-11+3\times 3\\&=3\times 4-11\end{aligned}}}

{\displaystyle {\begin{aligned}3m&\equiv 1\mod 11\\(4\times 3)m&\equiv 4\times 1\mod 11\\m&\equiv 4\mod 11\end{aligned}}}

${\displaystyle x=3m+2=3(11n+4)+2}$ ${\displaystyle x\equiv 2\mod 7}$

{\displaystyle {\begin{aligned}3(11n+4)+2&\equiv 2\mod 7\\33n+14&\equiv 2\mod 7\\33n&\equiv 2\mod 7\end{aligned}}}

{\displaystyle {\begin{aligned}33&=7\times 4+5\\7&=5\times 1+2\\5&=2\times 2+1\end{aligned}}}

{\displaystyle {\begin{aligned}1&=5-2\times 2\\&=5-(7-5\times 1)\times 2\\&=5\times 3-7\times 2\\&=(33-7\times 4)\times 3-7\times 2\\&=33\times 3-7\times 12-7\times 2\\&=33\times 3-7\times 14\end{aligned}}}

{\displaystyle {\begin{aligned}33n&\equiv 2\mod 7\\(3\times 33)n&\equiv 3\times 2\mod 7\\n&\equiv 6\mod 7\end{aligned}}}