中国剰余の定理

定理の紹介

中国の剰余定理は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理、孫子の定理とも呼ばれる。

『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。

定理について

　与えられた整数$m , n$が互いに素ならば、任意に与えられる整数$a, b$に対し、連立合同方程式
$x ≡ a (mod　m),$
$x ≡ b (mod　n)$
を満たす $x$ が $0$ 以上 $nm$ 未満の範囲に唯1つ存在する。

証明

連立合同式の解を2つあると仮定する。
それを$x, y$とおくと、
$x ≡ a_1 ≡ y　(mod　n)$
$x ≡ a_2 ≡ y　(mod　m)$
より$x - y$は$n$の倍数であり$m$の倍数でもある。
$n$と$m$が互いに素なので$x - y$は$nm$の倍数。
ところが$x, y$はともに$nm$未満の非不整数なので、$x = y$となり矛盾。
よって解が存在するとしたら１つ。
$n,m$は互いに素なので、$nX + mY = 1$を満たす整数$X, Y$が存在する。
よって、
$$ mY ≡ 1　(mod　n) nX ≡ 1　(mod　m) $$
よって、$x' = a_1mY + a_2nX$とおくと、
$x' ≡ a_1　(mod　n)$
$x' ≡ a_2　(mod　m)$
となりx'は題意の連立合同式を満たす。
$nm$未満の非負整数の解$x$を得るためには
$x$を$x'をnmで割った余り$とすればよい。

例題

・以下の合同連立方程式を解け。
$x ≡ 2 (mod　3)$
$x ≡ 4 (mod　5)$

解答

$3X + 5Y = 1$ を満たす $X,Y$ を直感またはユークリッドの互除法で求めると例えば, $X = 2, Y = −1$
よって $x′ = 2⋅5⋅(−1) + 4⋅3⋅2 = 14$

最後に

高校時代に私はこれを知りましたが、受験で使ったことは一回あるかないかくらいなので知らなくていいと思います。