前言

以前使用中国剩余定理看结论的。。
一直没有认真地取证明
以至于经常忘记
于是我今天就来证明一下这个东西

中国剩余定理

其实思路特别的简单
如果给你若干个同余方程
比方说3$3$个吧
x≡a1(modn1)$x\equiv a1(modn1)$
x≡a2(modn2)$x\equiv a2(modn2)$
x≡a3(modn3)$x\equiv a3(modn3)$
然后我们怎么构造呢？
我们可以先构造一个x1$x1$，使得x1$x1$是n1$n1$,n2$n2$的倍数，同时x1≡a3(modn3)$x1\equiv a3(modn3)$
这个不好构造，那么我们可以先构造一个x1≡1(modn3)$x1\equiv 1(modn3)$，那么x1∗a3$x1\ast a3$就是我们要的答案了
这个的话，我们先构造出一个n1,n2$n1,n2$的公倍数，一般情况下，暴力乘起来就可以了
然后怎么求一个x1≡1(modn3)$x1\equiv 1(modn3)$呢？
那么其实就是要求ax−b∗n3=1$ax-b\ast n3=1$
解不定方程就可以了
这个东西其实也是一个逆元的形式
于是就可以了
然后求出一个以后，显然地，x1+x2+.....xn$x1+x2+.....xn$就是一个符合要求的解了
但是这样看起来就不是一个最小的解
这个时候，我们只需要对[n1,n2,n3...nn]$[n1,n2,n\mathrm{3...}nn]$取膜就是答案了
当然，这个方法要求n互质
于是就得到了中国剩余定理的一般形式