中国剰余定理と法が互いに素でない場合への拡張

$k=1$ のときに成立するのは自明

$k=t$ のときに中国剰余定理が成立すると仮定すると，$t$ 本の合同式 $$x\equiv a_i \pmod{n_i}\:(i=1,\cdots, t)$$ を満たす $x$ の集合は，(うまく $x_0$ が取ってこれて) $1$ 本の合同式 $$x\equiv x_0\pmod{n_1n_2\cdots n_t}$$ を満たす $x$ の集合と同じ。

よって，今考えたい $t+1$ 本の連立合同式 $$x\equiv a_i \pmod{n_i}\:(i=1,\cdots, t+1)$$ は $2$ 本の連立合同式 $$x\equiv x_0\pmod{n_1n_2\cdots n_t}$$ $$x\equiv a_{t+1}\pmod{n_{t+1}}$$ と同値である。ここで，$n_1n_2\cdots n_t$ と $n_{t+1}$ は互いに素なので二元の場合の結果より，この連立合同式には解 $x$ が $0\leqq x <n_1n_2\cdots n_t\cdot n_{t+1}$ の範囲に存在する。

よって $k=t+1$ のときも中国剰余定理が成立するので，帰納法により証明完了。

解の唯一性は互いに素な場合と同様。以下，解の存在性を示す。右側の条件と一次不定方程式ax+by=cの整数解（ベズーの定理）より，

$n_1X+n_2Y=a_2-a_1$ を満たす整数 $X, Y$ が存在する（注）。

よって，$x'=n_1X+a_1=a_2-n_2Y$ とおくと $x'$ は連立合同式を満たす。最後に $x'$ を $\mathrm{lcm}(n_1,n_2)$ で割った余りを $x$ とすれば左側の条件を満たす。

連立合同式に解 $x$ が存在するとき，

$x\equiv a_1\pmod{n_1}$ であり，$n_1$ は $\mathrm{gcd}(n_1,n_2)$ の倍数なので

$x\equiv a_1\pmod{\mathrm{gcd}(n_1,n_2)}$

同様に $x\equiv a_2\pmod{\mathrm{gcd}(n_1,n_2)}$

となり右側の条件が満たされる。

$2n$ 個の素数 $p_1,\:p_2,\:,\cdots,\:p_{2n}$ を持ってくる。

中国剰余定理より，以下の $n$ 本の連立合同式を満たす $x$ が存在する。

$x\equiv -1\pmod{p_1p_2}$

$x\equiv -2\pmod{p_3p_4}$

$\cdots$

$x\equiv -n\pmod{p_{2n-1}p_{2n}}$

よって，$x+1,\:x+2,\:\cdots,x+n$ はいずれも2つ以上の素因数を持つので目標の主張は示された。