前言
约在2000多年以前，我国古代数学著作《孙子算经》中提出了著名的“物不知其数”问题：“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”答曰：“二十三”。
我国历史上还有很多人研究过这类问题，人们将这一类问题进一步发展和推广，并称之为“孙子定理”，在国外文献和教科书中称为“中国剩余定理”。
设物数为x，那么“物不知其数”问题相当于解如下形式的方程组：
$$
\left\{
\begin{array}{c}
x \equiv 2 (mod \ 3) \\
x \equiv 3 (mod \ 5) \\
x \equiv 2 (mod \ 7) \\
\end{array}
\right.
这种方程组我们称为同余方程组。
容易验证，当k使得上面每个同余式都成立时，所有模3x5x7=105同余于k的整数，也使得每个同余式成立，反过来，如果还有l使得同余方程组成立，那么，
$$l\equiv k(mod \ 3),l\equiv k(mod \ 5),l\equiv k(mod \ 7)$$.
于是$3 | l-k，5 | l-k，7 | l-k$，这表明l-k含有素因数3,5,7，从而$3 \times 5 \times 7 | l-k$，即$l\equiv k(mod \ 105)$.
通常，我们把$x\equiv k(mod \ 105)$叫做同余方程组额解，在这个意义下，同余方程只有一个解。
为了解同余方程组，我们首先建立拉格朗日插值公式。
拉格朗日插值法
例.你能否求一个多项式$f(x)$，使其满足$f(1)=1，f(-1)=3，f(2)=3$？
由二次函数的知识，先假设$f(x)=ax^2+bx+c$，代入可解得$f(x)=x^2-x+1$，利用这个多项式，我们可以写出所有满足条件的多项式
$$f(x)=x^2-x+1 + (x-1)(x+1)(x-2)h(x)$$.
其中$h(x)$是任意多项式.
下面介绍一种更为一般的方法——拉格朗日插值法，我们按如下步骤进行：
(1)求多项式$p(x)$，使$p(1)=1，p(-1)=0，p(2)=0$;
(2)求多项式$q(x)$，使$q(1)=0，q(-1)=1，q(2)=0$；
(3)求多项式$r(x)$，使$r(1)=0，r(-1)=0，r(2)=1$；
(4)作多项式$f(x)=1*p(x) + 3*q(x) + 3*r(x)$，它就是问题的一个解.
这里的$p(x)、q(x)、r(x)$好求吗？
如选取$p(x)=c(x+1)(x-2)$，其中$c$为常数，显然$p(-1)=0，p(2)=0$，再将$p(1)=1$代入，可求得$c$是$(1+1)(1-2)$的倒数，于是
$$p(x)=\frac{(x+1)(x-2)}{(1+1)(1-2)} = -\frac{1}{2} (x^2 -x -2).$$
同理可得
$$q(x)=\frac{(x-1)(x-2)}{(-1-1)(-1-2)} = \frac{1}{6} (x^2 -3x +2).$$
$$q(x)=\frac{(x-1)(x+1)}{(2-1)(2+1)} = \frac{1}{3} (x^2 - 1).$$
一般地，设$a，b，c$两两不同，那么满足$f(a)=e，f(b)=f，f(c)=g$的一个多项式$f(x)$可由下面的公式给出
$$f(x)=e\cdot p(x)+f\cdot q(x)+g\cdot r(x). \tag{(1)}$$
其中
$$p(x)=\frac{(x-b)(x-c)}{(a-b)(a-c)},q(x)=\frac{(x-a)(x-c)}{(b-a)(b-c)},r(x)=\frac{(x-a)(x-b)}{(c-a)(c-b)}. \tag{(2)}$$
通常，我们把公式(1)和(2)叫做拉格朗日插值公式.运用类似的方法，我们可以将它推广到一般情况.
解同余方程组
为了解同余方程组，我们依照建立拉格朗日插值公式的想法，按如下两个步骤进行：
1°求整数$p$，使$p\equiv 1(mod \ 3),p\equiv 0(mod \ 5),p \equiv 0(mod \ 7).$
求整数$q$，使$q\equiv 0(mod \ 3),q\equiv 1(mod \ 5),q \equiv 0(mod \ 7).$
求整数$r$，使$r\equiv 0(mod \ 3),r\equiv 0(mod \ 5),r \equiv 1(mod \ 7).$
2°作整数$k=2 \times p + 3 \times q + 2 \times r$，这个$k$使得方程组中每个同余式都成立.
此时，$x\equiv k(mod \ 3 \times 5 \times 7)$就是同余方程组的解.
如何求出$p、q$和$r$呢？不妨以求$p$为例.
由于$,p\equiv 0(mod \ 5),p \equiv 0(mod \ 7)$，故$5 | p,7 | p$，于是$p = 5 \times 7 \times c$，其中c是某个整数.再由$p\equiv 1(mod \ 3)$知，整数c满足：$5 \times 7 \times c\equiv 1(mod \ 3)$.而$5 \times 7 \equiv -1(mod \ 3)$，于是$-c \equiv 1(mod \ 3)$，进而$c \equiv 1(mod \ 3)$.若选取c=2，则p=70。
用类似的方法，我们可以得q=21，r=15.作整数$k=2 \times 70 + 3 \times 21 + 2 \times 15 = 223$，于是同余方程组得解为$x\equiv 233\equiv 23(mod \ 105)$.
一般地，我们有如下结论：
孙子定理：设$a,b,c$为两两互素的正整数，$e,f,g$为任意整数，则同余方程组
x \equiv e (mod \ a) \\
x \equiv f (mod \ b) \\
x \equiv g (mod \ c) \\
\right.
仅有一解：$x\equiv ebcc_1 + facc_2 + gabc_3 (mod \ abc)$，其中$c_1,c_2,c_3$为分别满足同余式：$bcc_1 \equiv 1(mod \ a),acc_2 \equiv 1(mod \ b),abc_3 \equiv 1(mod \ c)$的整数.
运用类似的方法，我们可以将孙子定理推广到更一般的情形.
例.（韩信点兵问题）有兵一队，若排成5行，则末行1人；若排成6行，则末行5人；若排成7行，则末行4人；若排成11行，则末行10人.求兵数。
解：先考虑第一种排列方式，设每行$t$个人，兵数为$x$，则$5t+1 = x$，所以$x≡1(mod \ 5)$.同理可得到另外3个式子.
x \equiv 1 (mod \ 5) \\
x \equiv 5 (mod \ 6) \\
x \equiv 4 (mod \ 7) \\
x \equiv 10 (mod \ 11) \\
利用孙子定理，设$p=6 \times 7 \times 11 \times c \equiv 1(mod \ 5) \Rightarrow 1 \times 2 \times 1 \times c \equiv 1(mod \ 5)\Rightarrow 2c\equiv 1(mod \ 5)$，取$c=3$，所以$p =6 \times 7 \times 11 \times 3$，同理可得到$q，r，t$.
$x\equiv 1 \times p + 5 \times q + 4 \times r + 10 \times t = 6731 \equiv 2111(mod \ 5 \times 6 \times 7 \times 11)$，即$x\equiv 2111(mod \ 2310)$.
个性签名：时间会解决一切