中国剰余定理が保証する連立合同式の解（前編）〜どのふたつも互いに素である場合〜

今まで

合同式の定義を扱った記事
フェルマーの小定理を証明した記事
倍数の判定法について解説した記事（前編と後編）

といったように、「合同式」にまつわる記事を書いてきました。

今回、この合同式シリーズのラスト（の予定）のテーマとして扱いたいのは「連立合同式」です。

私が高校生だった頃は「整数の性質」が学習指導要領の範囲外だったため、大学生になってから連立合同式を学びました。

これを現在の高校数学で扱っているということは、その近辺の理論が整理されていて、高校生が自由に解いて良いように問題を出題可能であるということです。

それらを保証する理論を初めて学んだとき、「分類」から生まれた合同式が「対応」によって本領を発揮している様子に感動した覚えがあります。

“中国剰余定理’’ と呼ばれる連立合同式の背景となっている定理について理解した上で、いくつかの問題を通して連立合同式を解ける嬉しさを感じていただければと思います。

本記事は【連立合同式シリーズ】の前編です。

後編はこちらの記事「中国剰余定理が保証する連立合同式の解（後編）　〜互いに素でないペアがある場合への拡張〜」をご覧ください。

我々が解きたい問題たち
1. 問題１
2. 問題２
高校数学の背後にある中国剰余定理
実際に問題１と２を解いてみる
最後に

我々が解きたい問題たち

本記事で我々が解きたい問題は以下の通りです。

事前に手を動かしてから読み進められると理解が深まると思います。

問題１

次の連立合同式を解け。
\begin{align*}
\begin{cases}
x\equiv 3 & \pmod 4\\
x\equiv 20 & \pmod {25}
\end{cases}
\end{align*}

問題２

次の連立合同式を解け。
\begin{align*}
\begin{cases}
x\equiv 1 & \pmod {16}\\
x\equiv 8 & \pmod {21}\\
x\equiv 7 & \pmod {25}
\end{cases}
\end{align*}

高校数学の背後にある中国剰余定理

定理を説明するための準備

$\mathbb{Z}$ を整数全体とします。

また、$2$ 以上の整数 $n$ に対して、$0$ から $n-1$ までの整数全体を $\mathbb{Z}_n$ と書くことにします。

（本来は、こちらの記事「合同式（mod）の成り立ち　〜well-definedの意味を考える〜」で紹介した剰余類の集合 $\mathbb{Z}/n\mathbb{Z}$ を考えて議論するのですが、簡単のために $\mathbb{Z}_n$ とします。）

ここで、$\mathbb{Z}$ から $\mathbb{Z}_n$ への数の対応 (写像) $\varphi_n$ を
$$
\varphi_n(x)=(x \mbox{を} n \mbox{で割った余り})
$$と定義します。

例えば、$1011$ を $5$, $7$, $8$ で割った余りはそれぞれ $1$, $3$, $3$ なので
\begin{align*}
\varphi_5(1011)&=1\\
\varphi_7(1011)&=3\\
\varphi_8(1011)&=3
\end{align*}と計算できます。

そこで、$(\varphi_5$, $\varphi_7$, $\varphi_8)$ をひとまとめにしましょう。

整数 $x$ に対して、上記の余りの組 $(\varphi_5(x), \varphi_7(x), \varphi_8(x))$ を与える対応 (写像) を $\Phi$ とします。

つまり、
$$
\begin{array}{ccc}
\mathbb{Z}&\longrightarrow&\mathbb{Z}_5\times\mathbb{Z}_7\times\mathbb{Z}_8\\
x&\longmapsto&\Phi(x)=(\varphi_5(x), \varphi_7(x), \varphi_8(x))
\end{array}
$$とします。

例えば、先程の例では
\begin{align*}
\Phi(1011)
&=(\varphi_5(1011), \varphi_7(1011), \varphi_8(1011))\\
&=(1,3,3)
\end{align*}と計算できます。

定理を考えるモチベーション

$2$ 以上の整数 $5$, $7$, $8$ に対して、各々の余りの組を対応させる $\Phi$
$$
x\ \longmapsto\ \Phi(x)=(\varphi_5(x), \varphi_7(x), \varphi_8(x))
$$を考えてきました。

このとき、$\Phi(x)=(1,3,3)$ なる整数 $x$ の一つとして $x=1011$ がとれていました。

そこで、

「$\Phi(x)=(1,3,3)$ なる整数 $x$ は他に存在するか」

という疑問が生じます。

つまり、

余りの組 $(r_1,r_2,r_3)$ から $\Phi$ の逆の対応によって
もとの整数 $x$ を復元できるか？

と考えるわけです。

$\Phi(x)=(r_1,r_2,r_3)$ を合同式によって書き直すと
\begin{align*}
\begin{cases}
x\equiv r_1 & \pmod {n_1}\\
x\equiv r_2 & \pmod {n_2}\\
x\equiv r_3 & \pmod {n_3}
\end{cases}
\end{align*}という連立合同式になります。

つまり、仮に先程の問題が解決されたなら

「この連立合同式の解を求めることができる！」

というわけです。

では、上記の問題を考えてゆきましょう。

定理の主張を理解しよう

法である $n_1$, $n_2$, $n_3$ にある条件を仮定することで問題に答えを与えるのが「中国剰余定理」（ちゅうごくじょうよていり）と呼ばれる定理です。

中国剰余定理は英語で Chinese remainder theorem といい、孫子の定理という別名もあります。

そんな定理の主張は以下の通りです。

– – – – –

法である $n_1$, $n_2$, $n_3$ のどのふたつも互いに素であるならば、任意の余りの組 $(r_1,r_2,r_3)$ に対して、$\Phi(x)=(r_1,r_2,r_3)$ なる整数 $x$ が…

$\mathbb{Z}_n$ の中に唯一つの解 $x_0$ が存在する。但し、$n=n_1n_2n_3$ である。
さらに、$n$ を法として $x_0$ と合同な数 $x$ が全ての解となる。

– – – – –

さて、イメージを共有しましょう。

整数のメモリが打ってある無限に伸びるものさしを三本準備します。

一本目は $1$ の位置と、そこから $5$ ずつずれた位置に印がついています。
二本目は $3$ の位置と、そこから $7$ ずつずれた位置に印がついています。
三本目は $3$ の位置と、そこから $8$ ずつずれた位置に印がついています。

印のついた数がそれぞれの合同式の解ですので、三本の印が同時についているような数が連立合同式の解になります。

ここで、法である $5$, $7$, $8$ のどのふたつも互いに素であるので、中国剰余定理が適用できます。

今、$n=5\times7\times8=280$ ですので、主張の１が

「$0$ から $279$ までの整数の中に三本の印が同時につくような数が存在すること」

を表しています。

また、主張の２が

「三本の印が同時につくような数の間隔は $280$ であること」

を表しています。

実際に問題１と２を解いてみる

問題を解くときの考え方

中国剰余定理から、解 $x_1$ がひとつでも見つかってしまえば $280$ を法として $x_1$ と合同な数 $x$ が全ての解となります。

今、$x_1=1011$ が解のひとつであることはわかっていましたから、解 $x$ は
$$
x\equiv 1011 \pmod {280}
$$と書くことができます。

これでも良いのですが、右辺の数は $\mathbb{Z}_{280}$ の中にある特別な解である $x_0$ にしておくと尚良いですね。

$1011$ から $280$ を可能な限り引いて余りを求めると $x_0=171$ となります。

よって、
$$
x\equiv 171 \pmod {280}
$$が最終的な答えとなります。

このように、法である $n_1$, $n_2$, $n_3$ のどのふたつも互いに素であるならば、中国剰余定理が適用できるため

とにかく、ひとつの解 $x_1$ を見つける。
$x_1$ と合同な $x_0\in\mathbb{Z}_n$ を求める。
求める解は $x\equiv x_0 \pmod n$ である。

のように連立合同式を解くことができるのです。

ポイントは「ひとつの解 $x_1$ を見つけること」になります。

実際の問題を通して、その見つけ方を考えてみましょう。

問題１を解く

問題１の連立合同式
\begin{align*}
\begin{cases}
x\equiv 3 & \pmod 4\\
x\equiv 20 & \pmod {25}
\end{cases}
\end{align*}を解いてみましょう。

法である $4$, $25$ は互いに素ですので中国剰余定理が適用できます。

互いに素であることから、ある解 $x_1$ は整数 $a$, $b$ を用いて
\begin{align}
x_1=25a+4b\tag{1}
\end{align}と書くことができます。（これが大事！）

さあ、$x_1$ を定めるために $a$, $b$ を定めましょう。

式 (1) について、$4$ を法として考えると
\begin{align*}
3&\equiv25a+4b\\
3&\equiv a+0\\
a&\equiv 3
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち $4$ を法とした合同式の右辺を持ってきています。）

式 (1) について、$25$ を法として考えると
\begin{align*}
20&\equiv25a+4b\\
-5&\equiv 0+4b\\
4b&\equiv -5\\
4b\times6&\equiv -5\times6\\
24b&\equiv -30\\
-b&\equiv -5\\
b&\equiv 5
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち $25$ を法とした合同式の右辺を持ってきています。）

これより、例えば $a=3$, $b=5$ とすることができます。

よって、式 (1) より
\begin{align*}
x_1
&=25\times3+4\times5\\
&=95
\end{align*}を得ます。

これは、$\mathbb{Z}_{100}$ に属していますので、$x_0$ は $95$ となります。

以上より、求める解は
$$
x\equiv95 \pmod {100}
$$となるのです。

問題２を解く

問題２の連立合同式
\begin{align*}
\begin{cases}
x\equiv 1 & \pmod {16}\\
x\equiv 8 & \pmod {21}\\
x\equiv 7 & \pmod {25}
\end{cases}
\end{align*}も同様に解いてみましょう。

法である $16$, $21$, $25$ はどのふたつも互いに素ですので中国剰余定理が適用できます。

$n=16\times21\times25$ とすると、どのふたつも互いに素であることから $\displaystyle \frac{n}{16}=21\times25$, $\displaystyle \frac{n}{21}=25\times16$, $\displaystyle \frac{n}{25}=16\times21$ は互いに素です。

よって、ある解 $x_1$ は整数 $a$, $b$, $c$ を用いて
\begin{align}
x_1
&=21\times25\times a\\
&\quad+25\times16\times b\\
&\quad+16\times21\times c\tag{2}
\end{align}と書くことができます。（これが大事！！）

さあ、$x_1$ を定めるために $a$, $b$, $c$ を定めましょう。

式 (2) について、$16$ を法として考えると
\begin{align*}
21\times25\times a&\equiv1\\
5\times(-7)\times a&\equiv1\\
-35a&\equiv1\\
-3a&\equiv1\\
a&\equiv5
\end{align*}となります。（一行目の右辺は、もとの連立合同式のうち $16$ を法とした合同式の右辺を持ってきています。）

式 (2) について、$21$ を法として考えると
\begin{align*}
25\times16\times b\equiv8\\
25\times2\times b\equiv1\\
4\times2\times b\equiv1\\
8b\equiv1\\
b\equiv8
\end{align*}となります。（一行目の右辺は、もとの連立合同式のうち $21$ を法とした合同式の右辺を持ってきています。）

式 (2) について、$25$ を法として考えると
\begin{align*}
16\times21\times c\equiv7\\
16\times3\times c\equiv1\\
(-9)\times3\times c\equiv1\\
-27c\equiv1\\
-2c\equiv1\\
c\equiv12
\end{align*}となります。（一行目の右辺は、もとの連立合同式のうち $25$ を法とした合同式の右辺を持ってきています。）

これより、例えば $a=5$, $b=8$, $c=12$ とすることができます。

よって、式 (2) より
\begin{align*}
x_1
&=21\times25\times5+25\times16\times8+16\times21\times12\\
&=9857
\end{align*}を得ます。

これを $n=8400$ で割った余りは $1457$ であるので、これが $x_0$ となります。

以上より、求める解は
$$
x\equiv1457 \pmod {8400}
$$となるのです。