中国剰余定理(存在と一意性)

まず2つの法の場合($k=2$)を証明し、帰納法で拡張する。$\gcd(m_1,m_2)=1$より、ベズーの等式から$m_1 u + m_2 v = 1$を満たす整数$u,v$が得られる。$x_0 = a_1 m_2 v + a_2 m_1 u$とおく。

法$m_1$で確認する:$m_1 u + m_2 v = 1$より$m_2 v = 1 - m_1 u \equiv 1 \pmod{m_1}$であり、一方$m_1 u \equiv 0 \pmod{m_1}$なので、$x_0 \equiv a_1\cdot 1 + a_2\cdot 0 = a_1 \pmod{m_1}$。

対称的に、法$m_2$では:$m_1 u = 1-m_2 v \equiv 1 \pmod{m_2}$かつ$m_2 v \equiv 0 \pmod{m_2}$なので、$x_0 \equiv a_1\cdot 0 + a_2\cdot 1 = a_2 \pmod{m_2}$。これで$k=2$での存在が証明された。

$k=2$での一意性:$x$と$x'$がともに連立系を解くなら、$x-x'\equiv0\pmod{m_1}$かつ$x-x'\equiv0\pmod{m_2}$、すなわち$m_1$と$m_2$はともに$d=x-x'$を割り切る。ベズーの式$m_1 u+m_2 v=1$に$d$を掛けると:$d = d m_1 u + d m_2 v$。$m_2\mid d$なので第1項$d m_1 u$は$m_1 m_2$の倍数であり、$m_1\mid d$なので第2項$d m_2 v$も$m_1 m_2$の倍数である。よって$m_1 m_2 \mid d$、すなわち$x\equiv x'\pmod{m_1 m_2}$である。

一般の$k>2$については帰納法による:最初の2つの合同式は($k=2$の場合により)$m_1 m_2$を法とする単一の合同式と同値である;$m_3$は$m_1$とも$m_2$とも互いに素なのでその積$m_1 m_2$とも互いに素であり、再び結合でき、以下$k$まで同様である。明示的な和$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$もまったく同じ理由で任意の$k$に対して直接機能することに注意せよ:$M_i = M/m_i$は$m_i$と互いに素なので逆元$y_i$が存在し、$j\neq i$なるすべての項は$M_j$の因数として$m_i$を含む。$\blacksquare$