中学入試にも頻出！その名も中国剰余定理！ - ラスクのMathematics for Everyone！

みなさま、こんにちは！

もう4月も中旬に差し掛かろうというのにまだまだ寒くてテンション下がり気味のラスクです↷↷
でも、今回がいよいよ本格的なブログの始動なのでテンション上げて頑張ります！！

最初という事で、内容は非常にシンプルなものを選びました。
なのでみなさま気軽な気持ちで読んでいってください！！

中学入試問題から
- 少し考察
いろいろな数で試すと…
- 余りを変える
- 割る数を変える
中国剰余定理
- なぜ成り立つのか
終わりに

中学入試問題から

まず今回のテーマに直結する次の問題を考えてみてください。

$4$ で割ると $2$ 余り、 $5$ で割ると $3$ 余る $2$ けたの整数のうち、もっとも大きい数を求めなさい。
(H18 麻布中学校)

いかがでしょうか？とてもシンプルな問題ですよね。
おそらくこの問題を見て文章の意味が分からないという方は少ないと思います。そして、このような問題が超名門校である麻布中学で出ているのです。ちなみに、ほとんど同じ問題(数字違うだけ)が、こちらも超名門校の灘中2008年にも出ています。
中学入試というと、何やら込み入った問題を方程式などを使わずに解くというイメージが強い方も多いのではないでしょうか。
でも、この問題を見ると、そういったものばかりではないことがわかっていただけるのではないかと思います。

さて、話が脱線しそうなので、以下この問題の解説をしています。

とりあえず問題文で言われた数を列挙してみましょう。

( $4$ で割って $2$ 余る数)： $2,6,10,14,{\bf 18},22,26,30,34,{\bf 38},42,46,50,54,{\bf 58},62,\ldots$
( $5$ で割って $3$ 余る数)： $3,8,13,{\bf 18},23,28,33,{\bf 38},43,48,53,{\bf 58},63,\ldots$

太字で書いたものが共通して出てくる数になり、そこだけに注目すれば $18$ から順に $20$ ずつ大きくなるのがわかるでしょう。
したがって、この問題の答えは、 $18+20\times4=98$ より $\underline{98}$ となります。*1

はい…それだけです。これのどこがおもしろいのでしょうか？(笑)
それは問題文に出てくる数字を少し変えることで見えてきます。

そこで以下では

$p_1$ で割って $r_1$ 余り、 $p_2$ で割って $r_2$ 余るような整数　（＊）

が存在するかどうか、という事を考えていきたいと思います。

少し考察

とその前に、今観察したことをまとめておきましょう。くどく感じるかもしれないですが、大事な所なので読んでみてください。

まず、最初の問題の条件を満たす数は $18$ から初めて $20$ おきに出てきました。この $20$ というのは、割る数である $p_1=4$ と $p_2=5$ の最小公倍数です。
一般に（＊）のような整数が何か一つ見つかれば、その数から $p_1$ と $p_2$ の最小公倍数( $L$ としましょう)だけずらしていった数も同じ性質を持ちます。

f:id:rusk_mathematics:20190415003723p:plain

このことから、何か一つ答えが見つかれば、その数から何度か $L$ を引く(あるいは足す)ことによって答えを $1$ から $L$ までの中に見つけることが出来ます。
先程の例でいえば、もし仮に $18$ より先に $38$ や $58$ という数が見つかってしまっても $20$ を何回か引くことによって $18$ を見つけることが出来るというわけです！

よって（＊）のようなものが存在するかどうかを考えるときは $1$ から $L$ までの数について調べればいいことになります！

さらに！
そんな $1$ から $L$ までの整数の中で（＊）の条件を満たすようなものはあるとしても一つだけです。
実際、二つの整数 $x_1,x_2$ がどちらも（＊）の条件を満たすとすると $x_1-x_2$ は $p_1$ と $p_2$ の公倍数となるので、 $x_1$ と $x_2$ は少なくとも $L$ だけ離れていなけらばならないのです。

これを言い換えれば、 $1$ から $L$ までの整数はそれぞれ異なる余りの組み合わせを実現するという事です。
これについてまだピンとこない人も、あまり気にせず続きを読んでみてください。

いろいろな数で試すと…

それでは、先ほど言った通り最初の問題の数を色々変えて実験してみましょう。

余りを変える

まずは、余りの組み合わせを変えてみて

$4$ で割ると $1$ 余り、 $5$ で割ると $4$ 余る整数

を考えてみましょう。この場合も先程と同様に数を列挙しますが、上の考察から $1$ から $20$ までの数を書けば十分でしたね？

( $4$ で割って $1$ 余る数)： $1,5,{\bf 9},13,17$
( $5$ で割って $4$ 余る数)： $4,{\bf 9},14,19$

無事に $9$ という数が見つかりました。
今、余りのパターンとして考えられるのは $4*5=20$ で $20$ 通りですが、そのすべてのパターンで試したものが下の表になります。

f:id:rusk_mathematics:20190415003810j:plain

どのパターンで試してもきちんと条件を満たす数が見つかりますことがわかりますね。ぜひみなさんもいくつか検算してみてください！

割る数を変える

では一方、割る数のほうを変えたらどうなるでしょう。

$3$ で割ると $2$ 余り、 $8$ で割ると $3$ 余る整数

というものを考えると、
( $3$ で割って $2$ 余る数)： $2,5,8,{\bf11},14,17,20,23$
( $8$ で割って $3$ 余る数)： $3,{\bf 11},19,$
となって無事に見つかりますが*2、

$4$ で割ると $2$ 余り、 $6$ で割ると $3$ 余る整数

というものは
( $4$ で割って $2$ 余る数)： $2,6,10$
( $6$ で割って $3$ 余る数)： $3,9$
となり $0$ から $12$ ( $4$ と $6$ の最小公倍数)までの間には見つかりません。すなわち、そんな整数は存在しないという事です。

このように割る数の方の組み合わせ( $p_1$ と $p_2$ )を変えると条件を満たす整数が存在したり、しなかったりすることがわかりました。

すると、当然の疑問として

「割る数がの組み合わせ( $p_1$ と $p_2$ )がどういったものなら、全ての余りの組み合わせ( $r_1$ と $r_2$ )に対して(＊)の条件を満たす整数が存在するのか？」

という事が気になりますよね？
実はそれを解決してくれるのが今回のテーマである中国剰余定理なのです！

中国剰余定理

定理の内容は以下の通りです。

定理
$p_1,p_2$ を正の整数とする。このときすべての $0\le r_1\lt p_1,0\le r_2\lt p_2$ に対して
$p_1$ で割って $r_1$ 余り、 $p_2$ で割って $r_2$ 余るような整数　（＊）
が存在するための必要十分条件は $p_1,p_2$ が互いに素であることである。

この定理の内容は読み取れますでしょうか？
前半の部分は今まで考えてた問題を改めて書いただけです。
そして後半に出てくる互いに素というキーワードですがこれが重要です。

二つの整数が互いに素とは、公約数を $1$ しか持たないということです。
そして、そのような整数 $p_1,p_2$ に対してのみ（＊）を満たすような整数がすべての余りの組み合わせに見つかるというのが定理の主張です。

確かに上で考えた例を見てみると、 $p_1=4,p_2=5$ や $p_1=3,p_2=8$ の場合はどちらも互いに素なので答えが見つかっていますが、 $p_1=4,p_2=6$ の場合は互いに素でない( $2$ という公約数を持つ)ので余りの組み合わせによっては答えが見つかりません。

ということで、なんとなく上の定理が正しそうな気がするわけですが、本当に正しいのかはもう少し考えなければいけません。
なので以下ではこの定理が成り立つ理由を説明していきます！

なぜ成り立つのか

といっても、先ほどの少し考察のところで述べたことを考えればすぐにわかります。
今、 $p_1,p_2$ を固定すると余りの組み合わせは $p_1\times p_2$ 通りあります。

また、
①（＊）を満たすような整数が存在するとすれば、 $1$ から $L$ の中にそのようなものがある。
② $1$ から $L$ の整数はそれぞれ別の余りの組み合わせを実現する。

のでした。

いま、
$p_1,p_2$ が互いに素であれば $L=p_1\times p_2$
そうでなければ $L\lt p_1\times p_2$
という事が成り立ちます。

よって
$p_1,p_2$ が互いに素であれば、余りの組み合わせの数と $L$ が一致します。このことと②のことを合わせれば、全ての余りの組み合わせに対応できることがわかります。
逆に $p_1,p_2$ が互いに素でなければ、余りの組み合わせの数よりも $L$ の方が小さいので、全ての余りの組み合わせには対応できないという事になります。

以上のことをまとめると下のようになります。

f:id:rusk_mathematics:20190415001759p:plain

これが中国剰余定理が成り立つ理由です。納得できましたでしょうか？

終わりに

という事で今回は
$p_1$ で割って $r_1$ 余り、 $p_2$ で割って $r_2$ 余るような整数
が存在するかどうかを考え、その結論である中国剰余定理を紹介しました。

複数の整数に関する初等的な性質を調べるときには互いに素かどうか、というのが重要になることが多いですが今回もそのうちの一つでした。ぜひ自分で何か $p_1$ と $p_2$ を選んで上に書いたような表を完成させてみてください。数学をやるうえで大事な力の一つに＜具体的にやってみる力＞というのがあると思います。なので今回も自分で手を動かすことによって、きっとこの定理がより深く理解できるはずです。

また、今回は存在性にのみ着目して、どのようにすれば答えが見つかるのかというのには触れませんでしたがそれに関しても面白い方法があるのでぜひ調べてみてください。

さて、最初なので丁寧にやり過ぎて、かなり長くなってしまっているので(笑)そろそろ終わりたいと思います。
いやぁ短くまとめるのは難しいですね、次からもっと頑張ります…

最後に、実は今回紹介した中国剰余定理はおそらくもっとも弱い形で述べられています。
しかし
これがもう少し一般化されても本質は今回説明した通りなので、次回（？）はもう少しこの内容を専門的に定式化するとどうなるのか、というのを見ていきたいと思います*3。お楽しみに！

コメントはどんなものでも絶賛受け付け中です！
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします！

それではまた次回お会いいたしましょう！

f:id:rusk_mathematics:20190415003905p:plain