中国剰余定理

定理

$n,m\in \mathbb{Z}$, 互いに素

$$\mathbb{Z}/mn\mathbb{Z}\cong \mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$$

証明

$$\begin{array}{rl}\rho :& \mathbb{Z}\to \mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}\\ & x\mapsto ([x{]}_{\mathbb{Z}/m\mathbb{Z}},[x{]}_{\mathbb{Z}/n\mathbb{Z}})\end{array}$$

が全射で, 準同型, $\ker \rho =mn\mathbb{Z}$ を示す

• 群準同型性
  定義から明らか

• 全射性
  ${}^{\forall }(a,b)\in (\mathbb{Z}/m\mathbb{Z},\mathbb{Z}/m\mathbb{Z})$ で $x\equiv a(\mathrm{mod}m),y\equiv b(\mathrm{mod}n)$ があれば良い.

$m\perp n$ より, $m{}^{\exists }u+n{}^{\exists }v=1$ が存在. ($\because$ ユークリッドの互除法), $x=anv+bmu$ が解になる.

• $\ker \rho =mn\mathbb{Z}$
  $\ker \rho \supset mn\mathbb{Z}$ は明らか(同値類なので)
  $m\perp n$ より, $\ker \rho \subset mn\mathbb{Z}$

参考文献

• 『耐量子暗号入門』 読書メモ