ここから本文です

「連立合同式 x≡1 (mod 3) , x≡2(mod 5) , x≡3 (mod 11)の整数解をすべて、求めよ...

dre********さん

2011/1/3022:27:41

「連立合同式 x≡1 (mod 3) , x≡2(mod 5) , x≡3 (mod 11)の整数解をすべて、求めよ」という問題の解き方が分かりません。どうやって、やればいいか教えてください。

因みに、中国剰余定理で用いてです。

閲覧数:
3,022
回答数:
1

違反報告

ベストアンサーに選ばれた回答

har********さん

2011/1/3105:10:29

中国剰余定理から,この連立合同式の整数解 x が存在し,
連立合同式を満たす整数のひとつを A とすると,
x = A + (3×5×11) z = A + 165 z (ただし,z は整数)
と書けます.

したがって,連立合同式を満たす整数解をひとつ探してくれば良いわけです.
さて,探し方はいろいろあります.



①地道に探す方法

x≡1 (mod 3) , x≡2(mod 5)をともに,満たす整数解をひとつ地道に探すと7.

したがって,この二つの連立合同式を満たす整数解 x は,

x≡7≡-8 (mod 15)

となります.ここで,x≡-8 (mod 15)とx≡3 (mod 11)をともに満たすxについて考えると,-8です.

したがって,この二つの連立合同式を満たす整数解 x は,

x≡-8≡157 (mod 165)

となるので,

x = 157 + 165 z (ただし,z は整数)

が三つの連立合同式を満たす整数解のすべてとなります.■

②ユークリッドの互助法の途中式を用いる方法

(5×11)a≡1 (mod 3)
(3×11)b≡1 (mod 5)
(3×5)c≡1 (mod 11)

となる a,b,c を探しましょう.もしこのa,b,cがわかれば,

55a≡1 (mod 3)
33b×2≡2 (mod 5)
15c×3≡3 (mod 11)

より,

55a+33b×2+15c×3≡1 (mod 3)
55a+33b×2+15c×3≡2 (mod 5)
55a+33b×2+15c×3≡3 (mod 11)

となりますから,55a+33b×2+15c×3がこの連立合同式を満たす整数解のひとつです.

さて,この a,b,c の求め方は,ユークリッドの互助法の途中式を用います.

まず55と3の最大公約数を求めるユークリッドの互助法の途中式は,

55=3×18+1

となるので,1=55×1+3×(-18).これより,a=1.

同様に33と5の最大公約数を求めるユークリッドの互助法の途中式は,

33=5×6+3

5=3×1+2

3=2×1+1

となるので,この途中式を用いて,

1=3-2×1
=3-(5-3×1)×1
=33-5×6-(5-(33-5×6)×1)×1
=33×2+5×(-13).

これより,b=2.

同様に15と11の最大公約数を求めるユークリッドの互助法の途中式は,

15=11×1+4
11=4×2+3
4=3×1+1

となるので,この途中式を用いて

1=4-3×1
=4-(11-4×2)×1
=(15-11×1)-(11-(15-11×1)×2)×1
=15×3-11×4

これより,c=3.

よって,

55a+33b×2+15c×3=55×1+33×2×2+15×3×3=322.

したがって,322≡157 (mod 165)に注意すれば,

x = 157 + 165 z (ただし,z は整数)

が三つの連立合同式を満たす整数解のすべてとなります.■

この回答は投票によってベストアンサーに選ばれました!

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる