こんにちは、リンス(@Lins016)です。
今回は中国剰余定理について学習していこう。
目次[表示]
中国剰余定理とは
中国の算術書「孫子算経」に「 3 3 で割ると 2 2 余り、 5 5 で割ると 3 3 余り、 7 7 で割ると 2 2 余る数は何か」という問題とその解法が書かれていた。
これを他の整数についても解けるように一般化したものが中国剰余定理と呼ばれるものなんだ。名前の由来はもちろん中国の算術書から。
この定理が高校数学ですごく有名ってことではなくて、この問題を合同式や 1 1 次不定方程式を利用して考えてみようってことで今回は記事を書いてるからね。
だから中国剰余定理の証明については書いてない。記事の最後に他サイトのリンクを貼ってるから証明について知りたい人はそっちを確認してほしい。
3 3 で割ると 2 2 余り、 5 5 で割ると 3 3 余り、 7 7 で割ると 2 2 余る数の求め方
・合同式の利用
・一次不定方程式の利用
・項の和の利用
だから今回は孫子算経に載っているその問題を考えてみよう。
3 3 で割ると 2 2 余り、 5 5 で割ると 3 3 余り、 7 7 で割ると 2 2 余る数を求めよ。
この問題を解く前に
という問題とは違うことを認識しておこう。
これを満たす数を n n とすると n+2 n+2 は 3 3 でも 5 5 でも 7 7 でも割り切れるよね。この問題みたいにある数をたすと割り切れるっていう風にはならないからね。
合同式の利用
合同式を利用して解いてみよう。
まずは合同式について復習しておこう。
-
割り算の余りの性質と合同式
割り算の余りを利用した計算や合同式の基本について詳しく解説しています。
続きを見る
{x≡2(mod3)⋯①x≡3(mod5)⋯②x≡2(mod7)⋯③
①より x=3k1+2 (k1∈Z)⋯④
これを②に代入すると
3k1+2≡3(mod5)
3k1≡1(mod5)
3k1≡6(mod5)
k1≡2(mod5)
∴k1=5k2+2 (k2∈Z)
これを④に代入して
x=3k1+2=15k2+8⋯⑤
これを③すると
15k2+8≡2(mod7)
15k2≡−6(mod7)
15k2≡1(mod7)
15k2≡15(mod7)
k2≡1(mod7)
∴k2=7k3+1 (k3∈Z)
これを⑤に代入して
x=15k2+8=105k3+23
よって求める答えは
105k+23 (k∈Z)
一次不定方程式の利用
次に一次不定方程式を使って解いてみよう。
一次不定方程式については次の記事を確認しておこう。
-
ユークリッドの互除法と一次不定方程式
一次不定方程式の解き方についてに詳しく解説しています。
続きを見る
{x=3k1+2⋯①x=5k2+3⋯②x=7k3+2⋯③
とおく
ただし、 ki∈Z, i=1, 2, 3, 4, 5, 6
3k1+2=5k2+3
3k1−5k2=1
5=3⋅1+2
3=2⋅1+1 より
1=3−2⋅1=3−(5−3⋅1)=3⋅2−5⋅1
3k1−5k2=1−)3⋅2−5⋅1=13(k1−2)−5(k2−1)=0
3(k1−2)=5(k2−1)
{k1=5k4+2⋯④k2=3k4+1⋯⑤
②, ③ より
3k1+2=7k3+2
④を代入し
3(5k4+2)+2=7k3+2
15k4−7k3=−6
15=7⋅2+1 より
1=15−7⋅2
15k4−7k3=−6−)15⋅(−6)−7⋅(−12)=−615(k4+6)−7(k3+12)=0
15(k4+6)=7(k3+12)
{k4=7k5−6⋯⑥k3=15k5−12⋯⑦
④, ⑥ より
k1=5(7k5−6)+2=35k5−28
① より
x=3(35k5−28)+2=105k5−82=105k6+23
よって求める答えは
105k+23 (k∈Z)
項の和を利用
次はあらかじめそれぞれの割った余りの項を作ってそれを足す方法を考えてみよう。
5×7×a を 3 で割ると 2 余る
3×7×b を 5 で割ると 3 余る
3×5×c を 7 で割ると 2 余る
これらを満たす数をそれぞれ求めると
a=1, b=3, c=2
この 3 つを足すと
これは 3 で割ると 2 余り、 5 で割ると 3 余り、 7 で割ると 2 余る数になるよね。
だってこの数は後ろに 2 つの項は 3 で割り切れるから、 3 で割った余りは最初の項を 3 で割った余りと同じになるよね。 5 で割ったとき、 7 で割ったときも同じように言えるよね。
これを満たす数は 3×5×7=105 を 1 周期として繰り返すから、 k, l を用いて（ k∈Z, l∈Z ）
105k+128=105l+23 とかけるんだ。
ただ、「 3×5×7=105 を 1 周期として繰り返す」とき、「 3 で割ると 2 余り、 5 で割ると 3 余り、 7 で割ると 2 余る数」が 1 周期に 1 つしかないことを言わないといけない。
3 で割った余りは 0, 1, 2 の 3 通り。
5 で割った余りは 0, 1, 2, 3, 4の 5 通り
7 で割った余りは 0, 1, 2, 3, 4, 5, 6の 7 通り
だから余りの組み合わせは 3×5×7=105 通りになる。
だから 1 周期に「 3 で割ると 2 余り、 5 で割ると 3 余り、 7 で割ると 2 余る数」は 1 つしか存在しない。
だから P−Q は 3 の倍数でもあるし、 5 の倍数でもあるし、 7 の倍数でもあるから、 105 の倍数ってことになる。
でも P, Q はどちらも 105 以下の数だから矛盾する。だから 2 つは存在しないことも言えるよね。
おまけ
ちなみに孫子算経の本文はこれ。
今有物、不知其数。
三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。
問物幾何?答曰:二十三。
術曰:『三・三数之、剰二』、置一百四十。『五・五数之、剰三』、置六十三。『七・ 七数之、剰二』、置三十。并之、得二百三十三。以二百一十減之、即得。凡、 三・三数之、剰一、則置七十。五・五数之、剰一、則置二十一。七・七数之、 剰一、則置十五。一百六以上、以一百五減之、即得。
ちなみに和算では未知の数を 3, 5, 7 でそれぞれ割った余りから元の数を求める計算を 3×5×7=105 から百五減算って読んでる。
中国剰余定理についてもっと詳しく知りたい人は次のページとか見てみるといいかも
-
中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ #競技プログラミング - Qiita
はじめに NTT データ数理システムでアルゴリズムの探求をしている大槻 (通称、けんちょん) です。最近のマイブームなアルゴリズムは NTT (Number-Theoretic Transform) ...
続きを見る
Point 中国剰余定理
①余りの問題は合同式や一次方程式を利用する
