中国剰余定理

存在。各 $i$ について
$$ M_i:=\frac{M}{m_i}=\prod_{j\neq i}m_j $$
とおく。$j\neq i$ なら $\gcd(m_i,m_j)=1$ なので、$m_i$ は積 $M_i$ とも互いに素である（互いに素 の記事の命題「互いに素な因子の消去」の 2 を繰り返す。$k=1$ なら $M_1=1$）。よって Bézoutの等式 により
$$ M_iy_i+m_iz_i=1 $$
となる整数 $y_i,z_i$ があり、$e_i:=M_iy_i$ とおくと $e_i\equiv1\pmod{m_i}$ である。また $j\neq i$ なら $m_j\mid M_i$ なので $e_i\equiv0\pmod{m_j}$ である。そこで
$$ x:=a_1e_1+a_2e_2+\cdots+a_ke_k $$
とおくと、各 $j$ について和の第 $j$ 項以外は $m_j$ を法として $0$ であり、$x\equiv a_je_j\equiv a_j\pmod{m_j}$ となる。よって $x$ は解である。
解全体。$x_0$ を解とする。$x=x_0+Mt$ なら、$m_i\mid M$ より $x\equiv x_0\equiv a_i\pmod{m_i}$ なので $x$ も解である。逆に $x$ が解なら、各 $i$ で $x\equiv a_i\equiv x_0\pmod{m_i}$、すなわち $m_i\mid x-x_0$ である。$m_1\cdots m_j\mid x-x_0$ を $j$ に関する帰納法で示す。$j=1$ は成り立っている。$m_1\cdots m_{j-1}\mid x-x_0$ とすると、$m_j$ は $m_1,\dots,m_{j-1}$ のそれぞれと互いに素なのでその積とも互いに素であり、$m_j\mid x-x_0$ と合わせて、互いに素 の記事の命題「互いに素な因子の消去」の 3 により $m_1\cdots m_j\mid x-x_0$ である。$j=k$ として $M\mid x-x_0$、すなわち $x\in x_0+M\mathbb{Z}$ である。$\square$

$x\equiv x'\pmod M$ なら $m_i\mid M$ より $x\equiv x'\pmod{m_i}$ なので、$\Phi$ は代表元の取り方によらず定まる。各成分 $x\bmod M\mapsto x\bmod m_i$ は和と積を保ち $1$ を $1$ に送るので、$\Phi$ は環準同型である。任意の $(a_1\bmod m_1,\dots,a_k\bmod m_k)$ に対し、thm-crt の解 $x$ は $\Phi(x\bmod M)=(a_1\bmod m_1,\dots,a_k\bmod m_k)$ を満たすので $\Phi$ は全射である。$\Phi(x\bmod M)=\Phi(x'\bmod M)$ なら $x$ と $x'$ は同じ連立合同式の解なので、thm-crt の後半により $x\equiv x'\pmod M$ であり、$\Phi$ は単射である。$\square$

解 $x$ があれば、$d\mid m_1\mid x-a_1$ かつ $d\mid m_2\mid x-a_2$ なので $d\mid a_1-a_2$ である。逆に $a_1-a_2=ds$（$s\in\mathbb{Z}$）とする。Bézoutの等式 により $m_1u+m_2v=d$ となる整数 $u,v$ がある。$x:=a_1-m_1us$ とおくと $x\equiv a_1\pmod{m_1}$ であり、
$$ x=a_1-(d-m_2v)s=a_1-ds+m_2vs=a_2+m_2vs $$
なので $x\equiv a_2\pmod{m_2}$ である。
解 $x_0$ を 1 つとる。$x$ が解であることは、$m_1\mid x-x_0$ かつ $m_2\mid x-x_0$、すなわち $x-x_0$ が $m_1,m_2$ の公倍数であることと同値である。公倍数は最小公倍数 $L$ の倍数にほかならない（$c$ を公倍数とし $c=qL+r$、$0\le r< L$ と割ると、$r=c-qL$ も公倍数なので $L$ の最小性から $r=0$）。よって解全体は $x_0+L\mathbb{Z}$ である。$\square$

素数 $p$ と $e\ge1$ について、$1\le a\le p^e$ の $a$ が $p^e$ と互いに素でないことは、$a$ が $p$ で割り切れることと同値である（$p^e$ の約数で $1$ より大きいものはすべて $p$ で割り切れる）。$p$ の倍数は $p,2p,\dots,p^{e-1}\cdot p$ の $p^{e-1}$ 個なので $\varphi(p^e)=p^e-p^{e-1}$ である。$p_1^{e_1},\dots,p_r^{e_r}$ は対ごとに互いに素であり、$p_1^{e_1}\cdots p_{j-1}^{e_{j-1}}$ と $p_j^{e_j}$ も互いに素なので、cor-crt-euler-phi を $r-1$ 回用いて $\varphi(n)=\prod_i\varphi(p_i^{e_i})$ を得る。最後の等式は $p^e-p^{e-1}=p^e(1-1/p)$ による。$\square$

$f(x)\equiv0\pmod{mn}$ であることは、$f(x)\equiv0\pmod m$ かつ $f(x)\equiv0\pmod n$ であることと同値である（$\Leftarrow$ は 互いに素 の記事の命題「互いに素な因子の消去」の 3）。$f(x)\bmod m$ は $x\bmod m$ だけで決まるので、thm-crt-iso の全単射 $x\bmod mn\mapsto(x\bmod m,\ x\bmod n)$ は、$mn$ を法とする解の集合を、$m$ を法とする解と $n$ を法とする解の組の集合へ全単射に写す。$\square$