RSSフィード
中国の剰余定理の使い方
中国の剰余定理(中国人の剰余定理)って、よく聞くし、印象にも残るんですが、それを使った問題の解き方を忘れがち。ということで、中国の剰余定理の定番問題を解いてみます。とりあえず、例題はこちら。
以下の連立合同式を解け
x≡1 mod 3
x≡2 mod 5
x≡3 mod 7
なんだか定番らしいと言うか、問題自体はシンプルで、ありがちです。
さて、ここで中国の剰余定理を使うと、答えが以下のような形になることが分かります。
x≡??? mod 105
105は、3,5,7の積です。ようするに、具体的にxが一つ定まるのではなく、105で割ったあまりが???なら何でも解になるということです。
つまり、中国の剰余定理は、連立合同式のそれぞれの式「x≡a mod m」のmどうしが互いに素のときに、解が存在して、「x≡??? mod m_1*m_2*…m_n」の形になることを教えてくれます。
つまるところ、実際の解の求め方を教えてくれるわけではないんですね。
さて、解いてみましょう。
まず、解はたくさんあるのですが、そのうちの一つを求めます。
その一つである「x」はどういう形になるかというと、こんな形になります。
x=a*5*7 + 3*b*7 + 3*5*c
ただし、以下を満たす
a*5*7 ≡ 1 mod 3
3*b*7 ≡ 2 mod 5
3*5*c ≡ 3 mod 7
実は、このa*5*7 + 3*b*7 + 3*5*cという数には秘密があって、a*5*7+3*(b*7 + 7*c)なので、3で割ると、a*5*7が余ります。同様にして、5で割ると3*b*7が、7で割ると3*5*cが余ります。
つまり、もし３つの条件を満たすのならば、xは確かに問題の連立合同式を満たすことになります。3で割ったら、a*5*7があまって、実はa*5*7自体を3で割ったら1あまるので、結果xを3で割ると1余るので。2つめ、3つめの式も同様です。
こんな説明で伝わるか気になるんですが、ここが一番重要だと思います。ちょっと考えてみてください。
さて、ここまできたら、解のうちの一つxを求めることは、a,b,cを求めることなのですが、 たとえば、aは次のようにして求めることができます。
a*5*7 ≡ 1 mod 3 より、
35a ≡ 1 mod 3
右辺に3をいくら足しても、3で割ったときのあまりは変わらないので、69を足して
35a ≡ 70 mod 3
両辺35で割ると、
a ≡ 2 mod 3
なんでここで69を足したのかというと、次のところで35で両辺を割って、左辺をaだけにしたかったからです。
同様に、
3*b*7 ≡ 2 mod 5
21b ≡ 2 mod 5
21b ≡ 2 + 5*8 mod 5
21b ≡ 42 mod 5
b ≡ 2 mod 5
3*5*c ≡ 3 mod 7
15c ≡ 3 mod 7
ここは3で割れるので
5c ≡ 1 mod 7にしてから
5c ≡ 1 + 7*2 mod 7
5c ≡ 15 mod 7
c ≡ 3 mod 7
ということで、以下のようになりました
a ≡ 2 mod 3
b ≡ 2 mod 5
c ≡ 3 mod 7
これを満たすa,b,cならなんでもいいので、a=2、b=2、c=3にしてみると、
2*5*7 ≡ 1 mod 3
3*2*7 ≡ 2 mod 5
3*5*3 ≡ 3 mod 7
なので、これを使うと、
x = 2*5*7 + 3*2*7 + 3*5*3(= 157)
これは、連立合同式を満たす解のうちの一つになっています。
連立合同式を満たす一つの解が分かったので、他の解を考慮した解は
x ≡ 2*5*7 + 3*2*7 + 3*5*3 ≡ 157 mod 105
x ≡ 52 mod 105
と、なります。これで問題が解けました！
仕組みを冷静に考えると、そんなに奇抜なことをやっているわけではありません。ただ、解の一つをa*5*7 + 3*b*7 + 3*5*cと置けばいいなんて思いつかないかもしれないですけどね。
