情報科学屋さんを目指す人のメモ(FC2ブログ版)

何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。

ブログ内検索

スポンサーサイト このエントリーを含むはてなブックマーク

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサー広告 | 編集
このエントリーをはてなブックマークに追加 Clip to Evernote

中国の剰余定理の使い方 このエントリーを含むはてなブックマーク

中国の剰余定理(中国人の剰余定理)って、よく聞くし、印象にも残るんですが、それを使った問題の解き方を忘れがち。ということで、中国の剰余定理の定番問題を解いてみます。とりあえず、例題はこちら。

以下の連立合同式を解け
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が余ります。

つまり、もし3つの条件を満たすのならば、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と置けばいいなんて思いつかないかもしれないですけどね。

数学・情報科学 | コメント:0 | トラックバック:0 | 編集
このエントリーをはてなブックマークに追加 Clip to Evernote

この記事のコメント

コメントの投稿 エントリの新旧に関わらず、極力18時間中に返信します。














この記事のトラックバック

トラックバックURL:
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。