考虑$\mathbb{Z}$上的线性同余方程组 $x \equiv a_i \bmod n_i$, 其中$i = 1, .., r$. 则该方程组有解, 当且仅当对于任意$i\not= j$, 都有$a_i \equiv a_j \bmod \text{gcd} (n_i, n_j)$.
证明. 首先我们列出几个引理:
引理1. 如果$a \equiv b \bmod m$ 并且 $n | m$, 则$a \equiv b \bmod n$.
引理2. 如果$a_1, a_2, …, a_r$都满足$a_i | n$, 则$\text{lcm}(a_1, …, a_r) | n$.
引理3. $\text{gcd}(\text{lcm} (a_1, …, a_r), b) = \text{lcm} (\gcd(a_1, b), …, \gcd(a_r, b))$.
引理的证明见文末.
假如存在$i \neq j$, 使得 $a_i \not \equiv a_j \bmod \text{gcd} (n_i, n_j)$, 则方程组无解. 这是因为假设有解$x$, 那么 $x \equiv a_i \bmod n_i$ 结合引理1得到 $x \equiv a_i \bmod \text{gcd}(n_i, n_j)$; 同理, $x \equiv a_j \bmod \text{gcd}(n_i, n_j)$. 因此 $a_i \equiv a_j \bmod \text{gcd}(n_i, n_j)$, 矛盾.
下面, 我们假定对于任意$i\not= j$, 都有$a_i \equiv a_j \bmod \text{gcd} (n_i, n_j)$. 我们来构造该方程组的解.
我们递推地构造该方程组的解, 即对于每个$k = 1,…, r$, 构造$x_k$使得$x_k$满足前$k$个方程构成的方程组.
当$k = 1$时, 显然可以取$x_1 = a_1$.
假定我们已经有了$x_k$满足前$k$个方程构成的方程组. 现在我们想构造$x_{k+1}$. 注意到, 如果令 $N_k = \text{lcm} (n_1, n_2, …, n_k)$, 那么$x_k + t N_k$能满足前$k$个方程构成的方程组, 其中$t$是任意整数. 这是因为$N_k \equiv 0 \bmod n_i$ 对于任意$i = 1, .., k$都成立.
我们因而可以令$x_{k+1} = x_k + t N_k$, 然后解符合条件的整数$t$, 即$x_k + t N_k \equiv a_{k+1} \bmod n_{k+1}$. 这等价于寻找整数$t, s$, 使得方程$t N_k + s n_{k+1} = - x_k + a_{k+1}$成立. 根据裴蜀定理, 这方程有解(由扩展欧几里得算法给出), 当且仅当$\text{gcd}(N_k, n_{k+1}) | (-x_k + a_{k+1})$.
这是成立的. 首先根据假设, 对于任意$i = 1, 2, .., k$, 都有$a_i \equiv a_{k+1} \bmod \gcd( n_i, n_{k+1} )$. 由于$x_k \equiv a_i \bmod n_i$, 我们知道 $x_k \equiv a_i \equiv a_{k+1} \bmod \gcd( n_i, n_{k+1} )$ (引理1) 进而 $\gcd(n_i, n_{k+1}) | (-x_k + a_{k+1})$. 接着由于引理2,
$$
\text{lcm} (\gcd(n_1, n_{k+1}), …, \gcd(n_k, n_{k+1})) | (-x_k + a_{k+1}).
$$
最后, 利用引理3, 我们得到欲证的$\text{gcd}(N_k, n_{k+1}) | (-x_k + a_{k+1})$.
这样, 我们就得到了需要的整数$t$, 使得$x_{k+1} = x_k + t N_k$. 证毕.
进一步, 如果令$N = N_r = \text{lcm}(n_1, …, n_r)$, 那么$x$在模$N$意义下是唯一的. 这是因为如果有两个解$x, x’$, 那么$x \equiv x’ \bmod n_i$ 对所有$i$都成立, 亦即$n_i | x - x’$. 利用引理2, 可知$N | x- x’$, 也就是$x \equiv x’ \bmod N$.
推论. 当对任意$i \neq j$, 都有$n_i$和$n_j$互质时, 条件$a_i \equiv a_j \bmod \text{gcd} (n_i, n_j)$恒为真 (因为任何整数$n$都有$n \equiv 0 \bmod 1$). 因此该同余方程组一定有解. 这就是中国剩余定理的常见形式.
引理的证明. 引理1和2都是显然的. 关于引理3, 我们可以先考虑这个关于整数$x, y, z$的恒等式:
$$
\min(\max(y, z), x) = \max(\min(y, x), \min(z, x)).
$$
它的证明可以通过枚举$x, y, z$的大小关系得到 (或者, 见我的这篇文章.). 它可以进一步被推广到
$$
\min(\max(y_1, …, y_r), x) = \max(\min(y_1, x), …, \min(y_r, x)),
$$
证明可以用数学归纳法完成 (此处从略). 最后, 只需注意到$\gcd$和$\text{lcm}$无非是把对应质因数的幂次取$\min$和$\max$.