中国剰余定理 (整数)

(定理) 中国剰余定理 (整数)

仮定

• \( k \) は自然数
• \( m_1, m_2, \cdots, m_k \) は整数であり、どの二つも互いに素
• \( a_1, a_2, \cdots, a_k \) は任意の整数

主張

を満たす整数 \( x \) が \( m_1m_2\cdots m_k \) を法として一意に存在する。

証明

次の補助定理を用いる:
二つの整数 \( m, n \) が互いに素であれば、任意に与えられる整数 \( a, b \) に対し、 \( x \equiv a ~(\mathrm{mod}~ m) \) かつ \( x \equiv b ~(\mathrm{mod}~ n) \) を満たす \( x \) が、 \( mn \) を法として一意に存在する。

この補助定理はユークリッドの互除法を用いて証明できる。ユークリッドの互除法を用いると、適当な整数 \( u, v \) が存在して、 \( mu + nv = 1 \) とできる。このとき \( mu \equiv ~(\mathrm{mod}~ n) \) かつ \( nv \equiv 1 ~(\mathrm{mod}~ m) \) が成立するので、 \( x \equiv anv + bmu ~(\mathrm{mod}~ mn) \) は解となる。

この解は一意である。 \( y \) も解であるとすると、 \( x - y \) について \( x - y \equiv 0 ~(\mathrm{mod}~ m) \) かつ \( x - y \equiv 0 ~(\mathrm{mod}~ n) \) が成立する。 \( m, n \) が互いに素であるから、これは \( x - y \) が \( mn \) で割り切れることを表す。これは \( x \) と \( y \) が法 \( mn \) に関して合同であることに他ならない。

この補助定理を帰納的に用いると、中国剰余定理も証明できる。