今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
上述问题便是一个具体线性同余方程组。所谓线性同余方程组，就是形如：
$$ \begin{cases} x \equiv a_{1} \pmod {m_{1}} \\ x \equiv a_{2} \pmod {m_{2}} \\ \vdots \\ x \equiv a_{n} \pmod {m_{n}} \end{cases} $$的方程组。
中国剩余定理 #
中国剩余定理是用于解决线性同余方程组的问题。 要使用中国剩余定理，必须得保证任意两个模数之间互质。
$$ x = \sum_{i = 1}^{n}a_iM_ib_i \\ $$其中，$M_i = \prod_{j = 1(i \neq j)}^{n}m_j$， $b_i$为 $M_i$的逆元。
对于中国剩余定理，我们可以这样理解：
对于方程组中，第 $i$个方程，如果能构造出这样一个解 $x_i$，使得 $x_i \equiv a_i \pmod {m_i}$，而 $x_i \equiv 0 \pmod {m_j} (i \neq j)$，那么最终方程组的答案就是 $\sum_{i = 1}^{n} x_i$。
$$ M_i b_i \equiv 1 \pmod {m_i} $$$$ a_i M_i b_i \equiv a_i \pmod {m_i} $$那么， $x_i = a_i M_i b_i$就是我们所需要构造的解了。
扩展中国剩余定理 #
当线性同余方程组中，存在两个模数不互质的时候，就要用到扩展中国剩余定理。 我们可以用数学归纳法来证明（理解/构造）扩展中国剩余定理。
首先，对于第一个方程，$x_1 = a_1$显然是第一个方程的解。
$$ x_k = x_{k - 1} + tm $$$$ \gcd{\{m, m_k\}} \mid a_k - x_{k - 1} $$时，同余方程有解。 整个过程就类似于两两个方程的解不断的合并，直到最后合并剩下最后一个解。
所以，当仅仅是判断方程组有没有解的情况，我们可以判断所有任意两个方程 $i, j$，判断是否满足 $\gcd{\{m_i, m_j\}} \mid a_i - a_j$。不满足时，整个方程组无解。