合同式シリーズの最後（の予定）の話題として扱ってきた「連立合同式」ですが、今回は、前回の結果を参考にして「中国剰余定理の一般化」をしたいと思います。
数学において、壮大な目標を掲げて証明を行いたいと思ったとき、まずは都合の良い条件を課して問題を簡単化して証明を行うことがあります。
その後、課した条件を少しずつ外してゆき、それにより生じた問題をそこまでに証明した事柄でクリアしてゆくのです。
このように、段階を踏むことは問題の解決において大切な考え方です。
前編で示した事柄が、その段階のひとつとして今回にどう活きてくるのか、意識して読み進めていただければと思います。
本記事は【連立合同式シリーズ】の後編です。
前編はこちらの記事「中国剰余定理が保証する連立合同式の解（前編） 〜どのふたつも互いに素である場合〜」をご覧ください。
我々が解きたい問題たち
本記事で我々が解きたい問題は以下の通りです。
事前に手を動かしてから読み進められると理解が深まると思います。
問題１
次の連立合同式を解け。
\begin{align*}
\begin{cases}
x\equiv 7 & \pmod {12}\\
x\equiv 13 & \pmod {30}
\end{cases}
\end{align*}
問題２
次の連立合同式を解け。
\begin{align*}
\begin{cases}
x\equiv 11 & \pmod {12}\\
x\equiv 17 & \pmod {42}\\
x\equiv 23 & \pmod {60}
\end{cases}
\end{align*}
前編で扱った内容の復習
前編で扱った内容を復習したいのですが、ここに改めて書いていると本記事が長くなりすぎるので、各自で前編の記事を適宜読み返していただければと思います。
その内容を一言で述べるならば
「どのふたつも互いに素であるような法を持つ連立合同式は、中国剰余定理によって解の存在性と一意性が保証されていた」
という内容でした。
法が互いに素でないときはどうなる？
ここからが本題です。
生じる不都合
法が互いに素でない場合は連立合同式を同様に解くことはできないのでしょうか？
例えば、
\begin{align*}
\begin{cases}
x\equiv 4 & \pmod 6\\
x\equiv 7 & \pmod {10}
\end{cases}
\end{align*}を考えてみましょう。
中国剰余定理の主張を説明した際に、ものさしの例え話をしました。
その考えからもわかるように、ひとつの解 \(x_1\) が見つかりさえすれば、解の間隔は \(6\) と \(10\) の最小公倍数の \(30\) であることが予想されます。
では「その解 \(x_1\) を見出だすこと」ができるでしょうか。
解 \(x_1\) が存在すると仮定しましょう。
ポイントとなるのは、中国剰余定理と、その説明の準備で導入した対応 (写像) \(\Phi\) です。
これにより、互いに素な法 \(n_1\), \(n_2\) と \(n=n_1n_2\) について、\(\mathbb{Z}_n\) と \(\mathbb{Z}_{n_1}\times\mathbb{Z}_{n_2}\) は一対一に対応するのでした。
法の最大公約数 \(2\) について考えましょう。
まず、\(x_1\equiv 4 \pmod 6\) なので、\(x_1\) に対応する \(\mathbb{Z}_2\) の要素は \(\varphi_2(4)=0\) となります。
一方、\(x_1\equiv 7 \pmod {10}\) なので、\(x_1\) に対応する \(\mathbb{Z}_2\) の要素は \(\varphi_2(7)=1\) となります。
これらは一致しなければなりません。
しかし、これらは等しくないので矛盾します。
つまり「この連立合同式の解は存在しない」というわけです。
以上で生じた問題点を取り除き、中国剰余定理の一般化を連立合同式の言葉で書いておきましょう。
解の存在条件
連立合同式
\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_i\) と \(n_j\) に対しても、その最大公約数を法として \(r_i\) と \(r_j\) が合同である」ならば \(\mathbb{Z}_n\) の中に唯一つの解 \(x_0\) が存在する。但し、\(n\) は \(n_1\), \(n_2\), \(n_3\) の最小公倍数である。
- さらに、\(n\) を法として \(x_0\) と合同な数 \(x\) が全ての解となる。
\(n_1\), \(n_2\), \(n_3\) のどのふたつも互いに素であるならば、主張１の仮定（条件１と呼びます）は任意の余りの組 \((r_1,r_2,r_3)\) に対して成り立ち、中国剰余定理の結論を得ます。
実際に連立合同式の問題を解くときは、条件１を確認して解が存在することがわかってから、互いに素である場合と同様に
- とにかく、ひとつの解 \(x_1\) を見つける。
- \(x_1\) と合同な \(x_0\in\mathbb{Z}_n\) を求める。
- 求める解は \(x\equiv x_0 \pmod n\) である。
のように解くことになります。
実際に問題１と２を解いてみる
問題１を解く
問題１の連立合同式
\begin{align*}
\begin{cases}
x\equiv 7 & \pmod {12}\\
x\equiv 13 & \pmod {30}
\end{cases}
\end{align*}を実際に解いてみましょう。
法である \(12\), \(30\) は互いに素ではないので中国剰余定理は適用できません。
そこで、条件１を確認しましょう。
- \(12\) と \(30\) の最大公約数 \(6\) を法として右辺の \(7\) と \(13\) は合同になります。
つまり、条件１は満足します！
これより、この連立合同式の解は存在するというわけです。
法である \(12\) と \(30\) の最小公倍数を \(n=60\) とします。
\(n\) を法とした解を見つけることになるのですが、\(n=2^2\times3\times5\) であるので、中国剰余定理より \(4\), \(3\), \(5\) を法とした値を求めれば良いですね。
勿論、\(\displaystyle \frac{n}{4}=3\times5\), \(\displaystyle \frac{n}{3}=4\times5\), \(\displaystyle \frac{n}{5}=4\times3\) は互いに素です。
よって、ある解 \(x_1\) は整数 \(a\), \(b\), \(c\) を用いて
\begin{align}
x_1=3\times5\times a+4\times5\times b+4\times3\times c\tag{1}
\end{align}と書くことができます。（これが大事！）
さあ、\(x_1\) を定めるために \(a\), \(b\), \(c\) を定めましょう。
式 (1) について、\(4\) を法として考えると
\begin{align*}
7&\equiv 3\times5\times a+4\times5\times b+4\times3\times c\\
-1&\equiv -a+0+0\\
a&\equiv 1
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(4\) で割り切れる数を法とした合同式の右辺を持ってきています。）
式 (1) について、\(3\) を法として考えると
\begin{align*}
7&\equiv 3\times5\times a+4\times5\times b+4\times3\times c\\
-2&\equiv 0-b+0\\
b&\equiv 2
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(3\) で割り切れる数を法とした合同式の右辺を持ってきています。）
式 (1) について、\(5\) を法として考えると
\begin{align*}
13&\equiv 3\times5\times a+4\times5\times b+4\times3\times c\\
3&\equiv 0+0+2c\\
2c&\equiv 3\\
2c\times3&\equiv 3\times3\\
6c&\equiv 9\\
c&\equiv -1
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(5\) で割り切れる数を法とした合同式の右辺を持ってきています。）
これら三式は独立しているので、例えば \(a=1\), \(b=2\), \(c=-1\) をとることができます。
よって、式 (1) より
\begin{align*}
x_1
&=3\times5\times1+4\times5\times2+4\times3\times(-1)\\
&=15+40-12\\
&=43
\end{align*}を得ます。
これを法になる \(n=60\) で割った余りは \(43\) 自身であるので、これが \(x_0\) となります。
以上より、求める解は
$$
x\equiv43 \pmod {60}
$$となります。
問題２を解く
問題２の連立合同式
\begin{align*}
\begin{cases}
x\equiv 11 & \pmod {12}\\
x\equiv 17 & \pmod {42}\\
x\equiv 23 & \pmod {60}
\end{cases}
\end{align*}も同様に解いてみましょう。
法である \(12\), \(42\), \(60\) は互いに素ではない法の組がありますので中国剰余定理は適用できません。
そこで、条件１を確認しましょう。
- \(12\) と \(42\) の最大公約数 \(6\) を法として右辺の \(11\) と \(17\) は合同になります。
- \(42\) と \(60\) の最大公約数 \(6\) を法として右辺の \(17\) と \(23\) は合同になります。
- \(60\) と \(12\) の最大公約数 \(12\) を法として右辺の \(23\) と \(11\) は合同になります。
以上より、条件１は満足します！
つまり、この連立合同式の解は存在するというわけです。
法である \(12\), \(42\), \(60\) の最小公倍数を \(n=420\) とします。
\(n\) を法とした解を見つけることになるのですが、\(n=2^2\times3\times5\times7\) であるので、中国剰余定理より \(4\), \(3\), \(5\), \(7\) を法とした値を求めれば良いですね。
勿論、\(\displaystyle \frac{n}{4}=3\times5\times7\), \(\displaystyle \frac{n}{3}=4\times5\times7\), \(\displaystyle \frac{n}{5}=4\times3\times7\), \(\displaystyle \frac{n}{7}=4\times3\times5\) は互いに素です。
よって、ある解 \(x_1\) は整数 \(a\), \(b\), \(c\), \(d\) を用いて
\begin{align}
x_1
&=3\times5\times7\times a\\
&\quad+4\times5\times7\times b\\
&\quad+4\times3\times7\times c\\
&\quad+4\times3\times5\times d\tag{2}
\end{align}と書くことができます。（これが大事！！）
さあ、\(x_1\) を定めるために \(a\), \(b\), \(c\), \(d\) を定めましょう。
式 (2) について、\(4\) を法として考えると
\begin{align*}
11 &\equiv 3\times5\times7\times a+0+0+0\\
-1 &\equiv a\\
a &\equiv -1
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(4\) で割り切れる数を法とした合同式の右辺を持ってきています。）
式 (2) について、\(3\) を法として考えると
\begin{align*}
11 &\equiv 0+4\times5\times7\times b+0+0\\
-1 &\equiv -b\\
b &\equiv 1
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(3\) で割り切れる数を法とした合同式の右辺を持ってきています。）
式 (2) について、\(5\) を法として考えると
\begin{align*}
23 &\equiv 0+0+4\times3\times7\times c+0\\
-2 &\equiv -c\\
c &\equiv 2
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(5\) で割り切れる数を法とした合同式の右辺を持ってきています。）
式 (2) について、\(7\) を法として考えると
\begin{align*}
17 &\equiv 0+0+0+4\times3\times5\times d\\
3 &\equiv -3d\\
-3d &\equiv 3\\
d &\equiv -1
\end{align*}となります。（一行目の左辺は、もとの連立合同式のうち \(7\) で割り切れる数を法とした合同式の右辺を持ってきています。）
これら四式は独立しているので、例えば \(a=-1\), \(b=1\), \(c=2\), \(d=-1\) をとることができます。
よって、式 (2) より
\begin{align*}
x_1
&=3\times5\times7\times(-1)\\
&\qquad+4\times5\times7\times1\\
&\qquad+4\times3\times7\times2\\
&\qquad+4\times3\times5\times (-1)\\
&=-105+140+168-60\\
&=143
\end{align*}を得ます。
これを法になる \(n=420\) で割った余りは \(143\) 自身であるので、これが \(x_0\) となります。
以上より、求める解は
$$
x\equiv143 \pmod {420}
$$となります。
最後に
今回は、中国剰余定理による一対一の対応を用いて、法が互いに素ではない場合について考察してきました。
一般の連立合同式が解ける条件、（条件１と呼んでいましたが）覚えていますでしょうか？
また、実際の問題を手を動かして解くことはできますでしょうか？
今回は合同式が \(2\), \(3\) 本の場合のみを扱うことで
- 条件１をチェックする。
- 元の連立合同式の法の最小公倍数 \(n\) を素因数分解し、素数の累乗が何種類あるか数える。(\(m\) 種類とする。)
- 解 \(x_1\) を、その \(m\) 個の素数の累乗を法とした法が互いに素である連立合同式の解として求めたいので、互いに素である \(m\) 個の整数 \(\displaystyle \frac{n}{\mbox{素数の累乗}}\) を係数とする整数 \(a_1, \cdots, a_m\) の和として \(x_1\) を表示する。
- その表示において \(m\) 個の素数の累乗を法として考え、各整数\(a_1, \cdots, a_m\) を上手く採用する。
- 求めた \(x_1\) と合同な \(x_0\in\mathbb{Z}_n\) について \(x\equiv x_0\pmod{n}\) が答えになる。
という方針を得ましたが、より多い \(4\) 本の場合や、一般に \(r\) 本の場合について通用するかの議論はみなさんの研究課題として残しておきたいと思います。
中国剰余定理も、その先の応用も、その理論自体は標準的な高校の授業で教わることはないでしょう。
しかし、それらの恩恵として、連立合同式という「楽しいパズル」が我々に与えられていると言えますね。
大学、大学院まで数学を学んだ私は、高校までの数学を「安全が保証された世界」と感じることがあります。
その “保証’’ が何によってなされているのか、今回のように考えを深められると見える世界が一変するかもしれません。
コメント