中国の剰余定理とは

/代数学

中国の剰余定理

中国の剰余定理とは、整数の剰余に関する定理で、中国の算術書「孫子算経」に由来するためこの名前がついています。2整数の場合は次のように言い表すことができます。

2つの整数 $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$ が互いに素(最大公約数が1)であれば、次の式を満たす整数 $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}$$

これより、②が成り立つことが分かります。

3整数以上の場合

中国の剰余定理は3整数以上の場合でも同様に成り立ちます。

$r$ 個の整数 $m_1,m_1,\cdots,m_r$ が互いに素なら、任意の正数 $a_1,a_2,\cdots,a_r$ に対して、以下を満たす解 $x_0$ が存在し、

$$x_0\equiv a_1\pmod{m_1} ,\cdots, x_0\equiv a_r\pmod{m_r}$$

次の式を満たす $x$ が存在することを示すことができます。

$$x\equiv x_0\pmod{m_1m_2\cdots m_r}$$

 

数学
解析学、代数学、幾何学、統計分析、数学基礎、物理数学
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

 

タイトルとURLをコピーしました