連立合同式

連立合同式が2つの時の解き方をおしえてください。
または、2つだとできないのでしょうか？？
問題は
x≡3(mod5)
x≡2(mod7)
答えは23です
2つで出来るのでしょうか？というより、学校でもらった資料ではできているのですが↓
どうかお願いします。

No.2 ベストアンサー 回答者： a_interest 回答日時： 2010/01/27 20:32

２つで解けますよ。

ユークリッドの互除法を用いれば簡単に解けます。

一応ユークリッドの互除法を用いずに簡単に説明しておきますね。

まず、剰余簡単な説明をしておきます。

剰余の簡単な意味は、たとえば x≡3(mod5) であれば、xは５で割って３余る数全体を指します。

具体的には 3,8,13,18,23,28,33…（全て5で割るとあまりが3になりますね)となり、式で書くと x = 5a + 3 (aは任意の整数)と表されます。

同様に x≡2(mod 7)のxは7で割って2余る数全体となります。

具体的には 2,9,16,23,30,37…（↑と同様７で割るとあまりが全て2)となり式で書くと x = 7b + 2 (bは任意の整数)と表されます。

上の数字列から、２つに共通している数が２３であることからxの解は２３ということが分かりますね。ただ、数学的に解くには２つの式からユークリッドの互除法という解き方を用います。一応ここまで描いておきますが、必要になったらユークリッドの互除法で検索してみてください。

この回答への補足

検索してもよくわからないです。
よく似たのはありますができません

補足日時：2010/01/27 22:20

No.1 回答者： f272 回答日時： 2010/01/27 20:29

x≡3(mod5)から7x≡21(mod35)

x≡2(mod7)から5x≡10(mod35)
この2つの連立合同式なら出来るかな？
7x≡21(mod35)から14x≡42≡7(mod35)
5x≡10(mod35)から15x≡30(mod35)