中国の剰余定理
中国の剰余定理とは、整数の剰余に関する定理で、中国の算術書「孫子算経」に由来するためこの名前がついています。２整数の場合は次のように言い表すことができます。
| ２つの整数 $m,n$ が互いに素なら、任意の正数 $a,b$ に対して、 $x_0\equiv a\pmod{m}$ 、 $x_0\equiv b\pmod{n}$ －① を満たす解 $x_0$ が存在し、かつ、次の式を満たす $x$ が存在する。 $x\equiv x_0\pmod{mn}$ －② |
①の証明
ユークリッド互除法より、整数 $m,n$ が互いに素（最大公約数が１）であれば、次の式を満たす整数 $r,s$ が存在します。
$$mr+ns=1 －③$$
$x_0$ を次のように置くと、
$$x_0=ans+bmr －④$$
③を使って④から $ns$ を消去すると、
$x_0=a+(b-a)mr$ 従って、 $x_0\pmod{m}\equiv a$
また、③を使って④から $mr$ を消去すると、
$x_0=b+(a-b)ns$ 従って、 $x_0\pmod{n}\equiv b$
これらより、①が成り立つことが分かります。
②の証明
$x$ も①の解とすると、
$$x\equiv x_0\equiv a\pmod{m}$$$$x\equiv x_0\equiv b\pmod{n}$$
従って、
$$x-x_0\equiv 0\pmod{m}$$$$x-x_0\equiv 0\pmod{n}$$
$m,n$ は互いに素であり、どちらでも割り切れるため、
$$x-x_0\equiv 0\pmod{mn}$$
これより、②が成り立つことが分かります。
３整数以上の場合
中国の剰余定理は３整数以上の場合でも同様に成り立ちます。
$r$ 個の整数 $m_1,m_2,\cdots,m_r$ が互いに素なら、任意の正数 $a_1,a_2,\cdots,a_r$ に対して、以下を満たす解 $x_0$ が存在し、
$$x_0\equiv a_1\pmod{m_1}$$$$x_0\equiv a_2\pmod{m_2}$$$$\cdots$$$$x_0\equiv a_r\pmod{m_r}$$
次の式を満たす $x$ が存在することを示すことができます。
$$x\equiv x_0\pmod{m_1m_2\cdots m_r}$$
