中国の余剰定理がわかりません。

質問

X≡2(mod6)
X≡4(mod8)
X≡2(mod14)
X≡14(mod15)

この問題が解けません。
どなたか教えてください。

回答No.5

ferien · ベストアンサー

解いてみました。

X≡2(mod6)
X≡4(mod8)
X≡2(mod14)
X≡14(mod15)
６＝２×３，８＝２^3，１４＝２×７，１５＝３×５
の最小公倍数は、２^3×３×５×７＝８４０
ｘ≡？（mod840）を求めます。
２^3，３，５，７を含んでいる式として
X≡4(mod8)
X≡2(mod14)
X≡14(mod15)
を連立させて解きます。
mod8で、ｘ1・１４・１５≡４
　　　　　２１０ｘ1≡４
　　　　　２ｘ1≡４
　　　　　　ｘ１≡２
mod14で、ｘ2・８・１５≡２
　　　　　１２０ｘ2≡２
　　　　　　８ｘ2≡１６
　　　　　　　ｘ2≡２
mod15で、ｘ3・８・１４≡１４
　　　　　１１２ｘ3≡１４
　　　　　　　７ｘ3≡１４
　　　　　　　　ｘ3≡２
ｘ＝２×１４×１５＋２×８×１５＋２×８×１４
　＝４２０＋２４０＋２２４
　＝８８４
ｘ≡４４（mod840）　となりました。
確かめ
４４＝６×７＋２より、44≡2(mod6)
４４＝８×５＋４より、44≡4(mod8)
４４＝１４×３＋２より、44≡2(mod14)
４４＝１５×２＋１４より、44≡14(mod15)
で、連立式の解になります。

どうでしょうか？

お礼

細かい解説ありがとうございました！
すごく参考になりました。

補足

２１０ｘ1≡４
２ｘ1≡４
の過程はどうやればいいのでしょうか？

回答No.6

ferien

No.5です。

×１（かける１）ではなくて、ｘ1（エックス１）です。紛らわしくて申し訳ありません。

＞２１０ｘ1≡４
＞２ｘ1≡４
＞の過程はどうやればいいのでしょうか？

２１０＝８×２６＋２なので、２１０≡２（mod8）です。
２１０ｘ1≡２ｘ1，２１０ｘ1≡４なので、
２ｘ1≡４です。

他の式変形の部分もだいたい同じ考え方です。
何かあったらお願いします。

回答No.4

ur2c

44, 884, 1724, 2564, 3404, 4244, 5084, 5924, 6764, 7604, 8444, 9284, ...

回答No.3

nag0720

X≡2(mod6)　⇔　X≡2(mod2) and X≡2(mod3)　⇔　X≡0(mod2) and X≡2(mod3)
X≡4(mod8)
X≡2(mod14)　⇔　X≡2(mod2) and X≡2(mod7)　⇔　X≡0(mod2) and X≡2(mod7)
X≡14(mod15)　⇔　X≡14(mod3) and X≡14(mod5)　⇔　X≡2(mod3) and X≡4(mod5)

整理すると、
X≡2(mod3)
X≡4(mod5)
X≡2(mod7)
X≡4(mod8)

同じ剰余は一緒にして、
X≡2(mod21)
X≡4(mod40)

これを解けばよい。

お礼

計算数を減らす方法を教えていただきありがとうございました。
計算数が減っていく分楽になりました。

回答No.2

Tacosan

たとえば
X≡2(mod6)
X≡4(mod8)
という連立合同式なら解けますか?

回答No.1

Tacosan

これはどう解釈すればいい?

4本個別? それとも全部まとめて 1つ? はたまた「上の 2本」と「下の 2本」で考える? ないしはそれ以外の何か?

「解けません」ということはいろいろ試したんだよね. どのような方法を試してみてどこで困った?

補足

まとめて一つです。
中国の余剰定理を知っていれば四つの合同式から一つの合同式を求めるということがわかると思ったので省略しました。