文献あり

初等整数論での中国剰余定理の証明

今回は、中国剰余定理についてやっていきます。連立合同式を解く手法として使われることが多い中国剰余定理を証明することを目的としています。証明をするのに必要となる準備をしてから本題に進みたいと思います。

中国剰余定理の証明の準備

これまでに書いてきた記事で証明した、あるいは登場した命題については証明を省略します。それ以外のものについては証明をなるべくするようにしているので、証明を見ずとも理解できている場合は飛ばしてもらって構いません。証明の中に証明がある部分がありますが、これは本を読んでいて少し行間があるように自分が感じた部分を勝手に補足しているものになります。

$a\mid b , b\mid c$なら、$a \mid c$である。
$m \ne 0$なら、$a \mid b \Leftrightarrow am \mid bm$

これはこれまでに何度か登場している命題の一つだと思います。

$a , b > 0$が整数なら、$gcd(a,b)lcm(a,b) = ab$である。

系1
$a , b > 0$が互いに素な整数なら、$lcm(a,b) = ab$である。

次の命題から証明をしていきます。

$a , a' , b , b' \in \mathbb{Z} \hspace{2mm},\hspace{2mm} m \in \mathbb{Z} \setminus \{0\}$とするとき、$a \equiv a' \hspace{2mm},\hspace{2mm} b \equiv b' \mod m$なら、
$$ a + b \equiv a' + b' \hspace{2mm},\hspace{2mm} ab \equiv a'b' \mod m$$
$a , b \in \mathbb{Z} , n ,m \in \mathbb{Z}\setminus \{0\} , n\mid m$とするとき、
$$ a \equiv b \mod m \rightarrow a \equiv b \mod n$$
$a , b\in \mathbb{Z} , n , m \in \mathbb{Z}\setminus \{0\}$とするとき、
$$ a \equiv b \mod n \rightarrow am \equiv bm \mod nm$$

証明

仮定より、$a - a' = mc \hspace{2mm},\hspace{2mm} b - b' = md \hspace{2mm}(c , d \in \mathbb{Z})$と表すことができる。
このとき、
$$ a - a' + b - b' = (a + b) - (a' + b') = m(c + d)$$
$$ ab - a'b' = a(b - b') + (a - a')b' = a\cdot md + mc \cdot b' = m(ad + cb')$$
となり、(1)が成り立つことが分かる。
$n \mid m$より、$m = nc$となるような整数$c$が存在する。
$$ a - b = mk = nck \hspace{2mm}(k \in \mathbb{Z})$$
と表せる。よって、$a \equiv b \mod m \rightarrow a \equiv b \mod n$が得られる。
仮定より、$a - b = nk \hspace{2mm}(k \in \mathbb{Z})$と書ける。
$am - bm = nmk$と表せ、結論を得る。□

系2
$m \in \mathbb{Z}\setminus \{0\} \hspace{2mm},\hspace{2mm} a,b,x,y \in \mathbb{Z}$とするとき、$a,b \equiv 0 \mod m$なら、$ax + by = 0 \mod m$である。したがって、$a,b$が$m$で割り切れるなら、$ax + by$も$m$で割り切れる。

証明は容易なため省略します。

系3
$a , b \in \mathbb{Z}\setminus \{0\}$なら、$a,b$の公約数は$gcd(a,b)$の約数である。また、$a,b$の公倍数は$lcm(a,b)$の倍数である。

証明
$-1$倍しても倍数・約数の関係は変化しないので、$a,b > 0$として考える。

$d = gcd(a,b)$とする。このとき、$ax + by = d$となる整数$x,y$が存在する。

$c$が$a,b$の公約数なら、系2より$d$も$c$で割り切れる。これにより系3の前半が示された。

($a,b$の公約数の中で最大のものが$d$なので、それより小さい公約数はすべて$d$を割り切る)

$l = lcm(a,b)$とする。命題2より$l = \dfrac{ab}{d}$である。

$a_1 = \dfrac{a}{d} , b_1 = \dfrac{b}{d}$とおくと、$a_1 , b_1$は互いに素である。

$c$が$a,b$の公倍数なら、$\dfrac{c}{d}$は$a_1,b_1$の公倍数になる。

最初の仮定から、$c$は$a,b$の公倍数なので、$c = ae = bf \hspace{2mm}(e,f \in \mathbb{Z})$と表せる。$a_1 = \dfrac{a}{d} , b_1 = \dfrac{b}{d}$とおいているので、$a = da_1 , b = db_1$となっているから、

$c = da_1e = db_1f$という結果が得られる。

$d$で割ってあげると、$\dfrac{c}{d} = a_1e = b_1f$となり、$a_1,b_1$の公倍数であることが分かる

$\dfrac{c}{d} = a_1e \hspace{2mm}(e \in \mathbb{Z})$とすると、$b_1 \mid e$である。

$c = da_1e = db_1f$より、当然、$da_1e = db_1f$が成り立つ。

両辺$d$で割ると、$a_1e = b_1f$.

$f \in \mathbb{Z}$であるから、$a_1e = b_1 \times$ (整数)という式の形となり、これはつまり、$b_1 \mid a_1e$であることを意味する。$a_1 , b_1$は互いに素であるので、$b_1 \mid e$であることが分かる。

$e = b_1g \hspace{2mm}(g \in \mathbb{Z})$とすると、$c = da_1e = da_1b_1g = lg$となるので、$l \mid c$である。

$l = \dfrac{ab}{d}$で、$a = da_1 , b = db_1$であるので、

$$ l = \dfrac{ab}{d} = \dfrac{da_1db_1}{d} = da_1b_1$$
となるので、

$c = da_1e = da_1b_1g = lg$

が得られる。

これにより後半も示された。□

中国剰余定理の証明

まずは、中国剰余定理とはどんな定理なのかを書いていきます。

(中国剰余定理)

$n_1,n_2 > 0$を互いに素な整数とするとき、次の(1),(2)が成り立つ。

$n_1x_1 + n_2x_2 = 1$となる$x_1 , x_2 \in \mathbb{Z}$を取る。任意の$a_1,a_2 \in \mathbb{Z}$に対し$a_0 = a_1n_2x_2 + a_2n_1x_1$とおくと、

$$ a_0 \equiv a_1 \hspace{3mm}\mod n_1$$
$$ a_0 \equiv a_2 \hspace{3mm}\mod n_2$$
(2) $a_0 \in \mathbb{Z}$に対して(1)の2式が成り立つとき、$a \in \mathbb{Z}$に対して(1)の2式が成り立つことと$a \equiv a_0 \mod n_1n_2$は同値である。

証明
(1) $n_2x_2 = 1 - n_1x_1$より、$a_0 = a_1(1 - n_1x_1) + a_2n_1x_1 \equiv a_1\hspace{2mm}\mod n_1$
同様に、$a_0 \equiv a_2 \mod n_2$となるので、$a_0$について(1)の2式が成り立つ。
(2) (1)の2式が成り立つような$a$を任意に取る。命題3より
$$ a - a_0 \equiv a_1 - a_1 \equiv 0 \mod n_1$$
となる。同様に、$a - a_0 \equiv 0 \mod n_2$.

よって、$a - a_0$は$n_1,n_2$の公倍数である。$n_1,n_2$は互いに素であるので、系1より$lcm(n_1 , n_2) = n_1n_2$

よって、系3より$a - a_0$は$n_1n_2$の倍数であることが分かり、$a \equiv a_0 \mod n_1n_2$となる。

逆に$a \equiv a_0 \mod n_1n_2$なら、命題3より$a$は(1)の性質を満たす。

$a \equiv a_0 \mod n_1n_2$より、$a - a_0 \equiv 0 \mod n_1n_2$である。
これはつまり、$a - a_0 = n_1n_2k \hspace{2mm}(k \in \mathbb{Z})$と表すことができる。なので、当然、$a - a_0 \equiv 0 \mod n_1 \hspace{2mm},\hspace{2mm}a - a_0 \equiv 0 \mod n_2$が成立することが分かる。

よって、同値であることが言えた。□

この命題4は2つの合同式についての話でしたが、一般の場合についても成り立ちます。それを保証するのが、次の定理です。

(中国剰余定理一般化)

$n_1,\cdots,n_t$を整数で、$i \ne j$なら、$n_i , n_j$は互いに素とする。
このとき、次の(1),(2)が成り立つ。
(1) $N = n_1\cdots n_t$とし、$\dfrac{N}{n_i}x_i + n_iy_i = 1$を満たす$x_1,\cdots ,x_t,y_1,\cdots,y_t \in \mathbb{Z}$をとり、
$$ a_0 = \sum_{i=1}^{t}\dfrac{N}{n_i}a_ix_i $$
とおくと、
$$ a_0 \equiv a_i \mod n_i \hspace{2mm}(i = 1,\cdots,t)$$
(2) $a_0 \in \mathbb{Z}$に対し、(1)の最後の式が成り立つとき、$a \in \mathbb{Z}$に対しこの式が成り立つことと$a \equiv a_0 \mod n_1\cdots n_t$は同値である。