中国剰余定理の証明と例題（二元の場合）

与えられた連立合同式の解が2つ以上あると仮定する。そのうちの2つを $x,y$ とおくと，

• $x\equiv a_1\equiv y \pmod{n_1}$
• $x\equiv a_2\equiv y\pmod{n_2}$

より $x-y$ は $n_1$ の倍数であり $n_2$ の倍数でもある。$n_1$ と $n_2$ が互いに素なので $x-y$ は $n_1n_2$ の倍数。

ところが $x,y$ はともに $n_1n_2$ 未満の非負整数なので $x=y$ となり矛盾。よって解が存在するとしたら $1$ つ。

$n_1, n_2$ は互いに素なので，

$n_1X+n_2Y=1$ を満たす整数 $X,Y$ が存在する(→注)。

よって，

$n_2Y\equiv 1\pmod{n_1}\\n_1X\equiv 1\pmod{n_2}$

よって，$x'=a_1n_2Y+a_2n_1X$ とおくと

$x'\equiv a_1\pmod{n_1}\\ x'\equiv a_2\pmod{n_2}$

となり $x'$ は与えられた連立合同式を満たす。

$n_1n_2$ 未満の非負整数の解 $x$ を得るためには $x$ を「$x'$ を $n_1n_2$ で割った余り」とすればよい。

$3X+5Y=1$ を満たす $X, Y$ を直感またはユークリッドの互除法で求めると，例えば $X=2, Y=-1$

よって解は $a_1n_2Y+a_2n_1X$ なので， $$x'=2\cdot 5\cdot (-1)+4\cdot 3\cdot 2=14$$

となる。