整数の性質

中国剰余定理

2020年5月1日

重要度 難易度

こんにちは、リンス(@Lins016)です。
今回は中国剰余定理について学習していこう。

中国剰余定理とは

中国の算術書「孫子算経」に「\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数は何か」という問題とその解法が書かれていた。

これを他の整数についても解けるように一般化したものが中国剰余定理と呼ばれるものなんだ。名前の由来はもちろん中国の算術書から。

この定理が高校数学ですごく有名ってことではなくて、この問題を合同式や\(\small{ \ 1 \ }\)次不定方程式を利用して考えてみようってことで今回は記事を書いてるからね。

だから中国剰余定理の証明については書いてない。記事の最後に他サイトのリンクを貼ってるから証明について知りたい人はそっちを確認してほしい。

中国剰余定理

\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数の求め方
・合同式の利用
・一次不定方程式の利用
・項の和の利用

だから今回は孫子算経に載っているその問題を考えてみよう。

例題を確認
問題

\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数を求めよ。

この問題を解く前に

\(\small{ \ 3 \ }\)で割ると\(\small{ \ 1 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 5 \ }\)余る数を求めよ。

という問題とは違うことを認識しておこう。
これを満たす数を\(\small{ \ n \ }\)とすると\(\small{ \ n+2 \ }\)は\(\small{ \ 3 \ }\)でも\(\small{ \ 5 \ }\)でも\(\small{ \ 7 \ }\)でも割り切れるよね。この問題みたいにある数をたすと割り切れるっていう風にはならないからね。

合同式の利用

合同式を利用して解いてみよう。
まずは合同式について復習しておこう。

CHECK
割り算の余りの性質と合同式-i
割り算の余りの性質と合同式

割り算の余りを利用した計算や合同式の基本について詳しく解説しています。

続きを見る

\(\small{\begin{eqnarray}
\left\{
\begin{array}{l}
x \equiv 2 \pmod 3\cdots① \\
x \equiv 3 \pmod 5\cdots②\\
x \equiv 2 \pmod 7\cdots③
\end{array}
\right.
\end{eqnarray}
\ }\)
\(\small{ \ ①}\)より\(\small{ \ x=3k_1+2 \ (k_1\in\mathbb{Z})\cdots④}\)
これを\(\small{ ②}\)に代入すると
\(\small{ \ 3k_1+2 \equiv 3 \pmod 5 \ }\)
\(\small{ \ 3k_1 \equiv 1 \pmod 5 \ }\)
\(\small{ \ 3k_1 \equiv 6 \pmod 5 \ }\)
\(\small{ \ k_1 \equiv 2 \pmod 5 \ }\)
\(\small{ \ \therefore k_1=5k_2+2 \ (k_2\in\mathbb{Z}) \ }\)
これを\(\small{④}\)に代入して
\(\small{\begin{eqnarray} \ x&=&3k_1+2\\
&=&15k_2+8\cdots⑤ \end{eqnarray}}\)
これを\(\small{③}\)すると
\(\small{ \ 15k_2+8 \equiv 2 \pmod 7 \ }\)
\(\small{ \ 15k_2 \equiv -6 \pmod 7 \ }\)
\(\small{ \ 15k_2 \equiv 1 \pmod 7 \ }\)
\(\small{ \ 15k_2 \equiv 15 \pmod 7 \ }\)
\(\small{ \ k_2 \equiv 1 \pmod 7 \ }\)
\(\small{ \ \therefore k_2=7k_3+1 \ (k_3\in\mathbb{Z}) \ }\)
これを\(\small{⑤}\)に代入して
\(\small{\begin{eqnarray} \ x&=&15k_2+8\\[3pt] &=&105k_3+23 \ \end{eqnarray}}\)
よって求める答えは
\(\small{ \ 105k+23 \ (k\in\mathbb{Z})}\)

一次不定方程式の利用

次に一次不定方程式を使って解いてみよう。
一次不定方程式については次の記事を確認しておこう。

CHECK
ユークリッドの互除法と一次不定方程式-i
ユークリッドの互除法と一次不定方程式

一次不定方程式の解き方についてに詳しく解説しています。

続きを見る

\(\small{\begin{eqnarray}
\left\{
\begin{array}{l}
x=3k_1+2\cdots① \\
x=5k_2+3\cdots②\\
x=7k_3+2\cdots③
\end{array}
\right.
\end{eqnarray} \ }\)
とおく
ただし、\(\small{ \ k_i\in\mathbb{Z}, \ i=1, \ 2, \ 3, \ 4, \ 5, \ 6 \ }\)
\(\small{ \ 3k_1+2=5k_2+3 \ }\)
\(\small{ \ 3k_1-5k_2=1 \ }\)
\(\small{ \ 5=3\cdot1+2 \ }\)
\(\small{ \ 3=2\cdot1+1 \ }\)より
\(\small{\begin{eqnarray} \ 1&=&3-2\cdot1\\[3pt] &=&3-(5-3\cdot1)\\[3pt] &=&3\cdot2-5\cdot1 \ \end{eqnarray}}\)
\(\small{\begin{eqnarray} \ &&3k_1&-&5k_2&=&1\\[3pt] &-)&3\cdot2&-&5\cdot1&=&1\\[3pt] \hline
&&3(k_1-2)&-&5(k_2-1)&=&0 \ \end{eqnarray}}\)
\(\small{ \ 3(k_1-2)=5(k_2-1) \ }\)
\(\small{\begin{eqnarray}
\left\{
\begin{array}{l}
k_1=5k_4+2\cdots④ \\
k_2=3k_4+1\cdots⑤
\end{array}
\right.
\end{eqnarray} \ }\)
\(\small{ \ ②, \ ③ \ }\)より
\(\small{ \ 3k_1+2=7k_3+2 \ }\)
\(\small{ \ ④}\)を代入し
\(\small{ \ 3(5k_4+2)+2=7k_3+2 \ }\)
\(\small{ \ 15k_4-7k_3=-6 \ }\)
\(\small{ \ 15=7\cdot2+1 \ }\)より
\(\small{ \ 1=15-7\cdot2 \ }\)
\(\small{\begin{eqnarray} \ &&15k_4&-&7k_3&=&-6\\[3pt] &-)&15\cdot(-6)&-&7\cdot(-12)&=&-6\\[3pt] \hline
&&15(k_4+6)&-&7(k_3+12)&=&0 \ \end{eqnarray}}\)
\(\small{ \ 15(k_4+6)=7(k_3+12) \ }\)
\(\small{\begin{eqnarray}
\left\{
\begin{array}{l}
k_4=7k_5-6\cdots⑥\\
k_3=15k_5-12\cdots⑦
\end{array}
\right.
\end{eqnarray} \ }\)
\(\small{ \ ④, \ ⑥ \ }\)より
\(\small{\begin{eqnarray} \ k_1=5(7k_5-6)+2\\
=35k_5-28 \ \end{eqnarray}}\)
\(\small{ \ ① \ }\)より
\(\small{\begin{eqnarray} \ x&=&3(35k_5-28)+2\\
&=&105k_5-82\\
&=&105k_6+23 \ \end{eqnarray}}\)
よって求める答えは
\(\small{ \ 105k+23 \ (k\in\mathbb{Z})}\)

項の和を利用

次はあらかじめそれぞれの割った余りの項を作ってそれを足す方法を考えてみよう。
\(\small{ \ 5\times7\times a \ }\)を\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余る
\(\small{ \ 3\times7\times b \ }\)を\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余る
\(\small{ \ 3\times5\times c \ }\)を\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る
これらを満たす数をそれぞれ求めると
\(\small{ \ a=1, \ b=3, \ c=2 \ }\)

point
\(\small{ \ 3\times7\times b \ }\)を\(\small{ \ 5 \ }\)で割った余りを考えるとき、\(\small{ \ 3\times7 \ }\)を\(\small{ \ 5 \ }\)で割った余りは\(\small{ \ 1 \ }\)だから、これを\(\small{ \ b \ }\)倍したとき割った余りは\(\small{ \ b \ }\)を割った余りと同じになるよね。だから\(\small{ \ 5 \ }\)で割った余りが\(\small{ \ 3 \ }\)になるのは\(\small{ \ b=3 \ }\)なんだ。

この\(\small{ \ 3 \ }\)つを足すと

\(\small{ \ (5\times7\times1)+(3\times7\times3)+(3\times5\times2)=128 \ }\)

これは\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数になるよね。
だってこの数は後ろに\(\small{ \ 2 \ }\)つの項は\(\small{ \ 3 \ }\)で割り切れるから、\(\small{ \ 3 \ }\)で割った余りは最初の項を\(\small{ \ 3 \ }\)で割った余りと同じになるよね。\(\small{ \ 5 \ }\)で割ったとき、\(\small{ \ 7 \ }\)で割ったときも同じように言えるよね。

これを満たす数は\(\small{ \ 3\times5\times7=105 \ }\)を\(\small{ \ 1 \ }\)周期として繰り返すから、\(\small{ \ k, \ l \ }\)を用いて(\(\small{ \ k\in\mathbb{Z}, \ l\in\mathbb{Z} \ }\))
\(\small{ \ 105k+128=105l+23 \ }\)とかけるんだ。

ただ、「\(\small{ \ 3\times5\times7=105 \ }\)を\(\small{ \ 1 \ }\)周期として繰り返す」とき、「\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数」が\(\small{ \ 1 \ }\)周期に\(\small{ \ 1 \ }\)つしかないことを言わないといけない。

\(\small{ \ 3 \ }\)で割った余りは\(\small{ \ 0, \ 1, \ 2 \ }\)の\(\small{ \ 3 \ }\)通り。
\(\small{ \ 5 \ }\)で割った余りは\(\small{ \ 0, \ 1, \ 2, \ 3, \ 4}\)の\(\small{ \ 5 \ }\)通り
\(\small{ \ 7 \ }\)で割った余りは\(\small{ \ 0, \ 1, \ 2, \ 3, \ 4, \ 5, \ 6}\)の\(\small{ \ 7 \ }\)通り
だから余りの組み合わせは\(\small{ \ 3\times5\times7=105 \ }\)通りになる。
だから\(\small{ \ 1 \ }\)周期に「\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数」は\(\small{ \ 1 \ }\)つしか存在しない。

point
ちなみに\(\small{ \ 3 \ }\)で割ると\(\small{ \ 2 \ }\)余り、\(\small{ \ 5 \ }\)で割ると\(\small{ \ 3 \ }\)余り、\(\small{ \ 7 \ }\)で割ると\(\small{ \ 2 \ }\)余る数が\(\small{ \ 1〜105 \ }\)の中に\(\small{ \ 2 \ }\)つあるとして、その数を\(\small{ \ P, \ Q \ }\)としてみよう。\(\small{ \ P-Q \ }\)は\(\small{ \ 3 \ }\)でも\(\small{ \ 5 \ }\)でも\(\small{ \ 7 \ }\)でも割り切れるよね。
だから\(\small{ \ P-Q \ }\)は\(\small{ \ 3 \ }\)の倍数でもあるし、\(\small{ \ 5 \ }\)の倍数でもあるし、\(\small{ \ 7 \ }\)の倍数でもあるから、\(\small{ \ 105 \ }\)の倍数ってことになる。

でも\(\small{ \ P, \ Q \ }\)はどちらも\(\small{ \ 105 \ }\)以下の数だから矛盾する。だから\(\small{ \ 2 \ }\)つは存在しないことも言えるよね。

おまけ

ちなみに孫子算経の本文はこれ。

今有物、不知其数。
三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。
問物幾何?答曰:二十三。
術曰:『三・三数之、剰二』、置一百四十。『五・五数之、剰三』、置六十三。『七・ 七数之、剰二』、置三十。并之、得二百三十三。以二百一十減之、即得。凡、 三・三数之、剰一、則置七十。五・五数之、剰一、則置二十一。七・七数之、 剰一、則置十五。一百六以上、以一百五減之、即得。

ちなみに和算では未知の数を\(\small{ \ 3, \ 5, \ 7 \ }\)でそれぞれ割った余りから元の数を求める計算を\(\small{ \ 3\times5\times7=105 \ }\)から百五減算って読んでる。

中国剰余定理についてもっと詳しく知りたい人は次のページとか見てみるといいかも

他のサイトへ
中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita
中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

続きを見る

Point 中国剰余定理

①余りの問題は合同式や一次方程式を利用する

この記事が気に入ったら
いいね ! しよう

Twitter で

 整数の性質

 , ,

  • この記事を書いた人
  • 最新記事

リンス

名前:リンス
職業:塾講師/家庭教師
性別:男
趣味:料理・問題研究
好物:ビール・BBQ

Copyright© 高校数学.net , 2020 All Rights Reserved.