§A4.6中国剰余定理

証明.§A4.3 補題 1.1により、$mu+nv=1$を満たす整数$u,v$が存在する。$nv\equiv1\pmod m$、$mu\equiv1\pmod n$であるから、$x_0=anv+bmu$は二つの合同式を満たす。

整数$x$も二つの合同式を満たすなら、ある整数$s,t$によって$x-x_0=ms=nt$と書くことができる。したがって、

であり、$x\equiv x_0\pmod{mn}$が成り立つ。逆に、$x\equiv x_0\pmod{mn}$なら、$m$と$n$はともに$x-x_0$を割り切るので、$x$は二つの合同式を満たす。▨

証明.$r=2$の場合は補題 2.1による。$k\ge2$とし、$r=k$の場合に主張が成り立つと仮定する。帰納法の仮定により、最初の$k$個の合同式は、ある整数$c$と$P=m_1\cdots m_k$を用いて$x\equiv c\pmod P$とまとめることができる。

$P$と$m_{k+1}$に$1$より大きい公約数があれば、§A4.2 定理 2.2により、その公約数に素因子$p$が存在する。$p$は$P$と$m_{k+1}$をともに割り切り、§A4.2 補題 2.1を繰り返し用いると、$p$は$m_1,\ldots,m_k$のいずれかも割り切る。これは法がどの二つも互いに素であることに反するので、$P$と$m_{k+1}$は互いに素である。補題 2.1により、$x\equiv c\pmod P$と$x\equiv a_{k+1}\pmod{m_{k+1}}$は、法$Pm_{k+1}$の一つの合同式にまとめることができる。数学的帰納法により、すべての整数$r\ge2$について主張が成り立つ。▨