中国剩余定理的证明

方法一（直接构造）：
由m,n互素，存在u,v使得u*m+v*n=1（裴蜀定理）。令x=v*n*a+u*m*b，则一方面，x=(v*n)*a+u*m*b=(1-u*m)*a+u*m*b=a-u*m*a+u*m*b=(u*b-u*a)*m+a；另一方面，x=v*n*a+(u*m)*b=v*n*a+(1-v*n)*b=v*n*a+b-v*n*b=(v*a-v*b)*n+b。取p=u*b-u*a，q=v*a-v*b即可。
如果这样得到的x不是正的，可以加上m*n的足够多倍，不改变除以m或n所得的余数。

方法二（鸽巢原理）：
定义集合S={0,1,...,m*n-1}，A={0,1,...,m-1}，B={0,1,...,n-1}；定义映射f:S->A*B：对任意x属于S（0<=x<=m*n-1），f(x)的第一个分量为x除以m的余数，第二个分量为x除以n的余数。则原命题等价于f是满射。

声明：f为单射。
证明：假设存在x,y属于S使得f(x)=f(y)，即x除以m的余数等于y除以m的余数，x除以n的余数等于y除以n的余数。前面说明x-y被m整除，后面说明x-y被n整除，所以x-y能够被m和n的最小公倍数整除。由m,n互素，最小公倍数即为m*n，所以x-y能够被m*n整除。但由0<=x,y<=mn-1知-(m*n-1)<=x-y<=m*n-1。唯一的可能是x-y=0，即x=y。从而f是单射。

S中有m*n个元素，A*B中也有m*n个元素，f为S到A*B的单射，所以由鸽巢原理，f也是满射。证毕。