- 締切済み
連立1次合同式の解き方がよくわかりません。
連立1次合同式の解き方がよくわかりません。 整数xの連立１次合同式を解きなさい。 5x ≡ 7 (mod11) 3x ≡ 5 (mod19) という問題です。 途中式と答えを教えてください。 よろしくお願いします。
- 1234567kkk
- お礼率36% (8/22)
- 数学・算数
- 回答数6
- ありがとう数0
- みんなの回答 （6）
- 専門家の回答
みんなの回答
- muturajcp
- ベストアンサー率78% (505/644)
5x=7(mod11) の両辺に5のmod11での乗法逆元5^{-1}を掛けると x=(5^{-1})7(mod11) となるから5^{-1}を求めるため 5,11に対して互除法を使う 11=2*5+1 11-2*5=1 -2*5=1(mod11) 5のmod11での乗法逆元は-2 だから 5x=7(mod11) の両辺に-2を掛けると x=-2*5x=-2*7=-14=11*2-14=8(mod11) 3x=5(mod19) 3のmod19での乗法逆元3^{-1}を両辺に掛けると x=(3^{-1})5(mod19) となるから3^{-1}を求めるため 3,19に対して互除法を使う 19=6*3+1 19-6*3=1 -6*3=1(mod19) 3のmod19での乗法逆元は-6 だから 3x=5(mod19) の両辺に-6を掛けると x=-6*3x=-6*5=-30=19*2-30=8(mod19) x=8(mod11) x=8(mod19) 11,19は互いに素で11*19=209だから 中国の剰余定理から ∴ x=8(mod(209))
- 178-tall
- ベストアンサー率43% (762/1732)
蛇足。 > x ≡ a (mod 11) > x ≡ b (mod 19) にて a=b=8 。 >しかし、文字で区別しておかないと解法の仕掛けが見えにくい。 a=b=8 の場合なら、 x = 8 + 11s x = 8 + 19t ということです。 一目で、s=19, t=11 ですよネ。 つまり、 x = 8 + 11*19 これは、 x ≡ 8 (mod 11*19) を意味する。 「孫子定理」は「これが一意解である」と保証してくれるだけ…。
- 178-tall
- ベストアンサー率43% (762/1732)
現題は、 x ≡ a (mod 11) x ≡ b (mod 19) にて a=b=8 。 しかし、文字で区別しておかないと解法の仕掛けが見えにくい。 >あとは「孫子の剰余定理」？ 実は、「剰余定理」を眺めても「一意的な解が存在する」ことしか判りません。 解法の一例だけ。 まず、11y ≡ 1 (mod 19) の解を求めておく。 11y + 19z = 1 から、y = 7 (z = -4) 。 d = (b-a)y として現題の連立解は、x = a + 11d である。 実際、 x = a + 11d = a + 11(b-a)y ≡ a + (b-a) = b (mod 19) と、連立解になっている。 現題では a=b なので、x ≡ a = 8 (mod 11*19) 。
- 178-tall
- ベストアンサー率43% (762/1732)
>5x ≡ 7 (mod11) >3x ≡ 5 (mod19) >中国の剰余定理を使って解くのです。 …ということは、互除法はお手のものですね。 5x ≡ 7 (mod11) から、x = -14 + 11z を得て体裁つければ、x ≡ 8 (mod11) 。 同様にして、x = -30 + 19z → x ≡ 8 (mod19) 。 あとは「孫子の剰余定理」？
- asuncion
- ベストアンサー率33% (2126/6288)
＞申し訳ございませんが、中国の剰余定理を使って解くのです。 そういう、後出しジャンケンのような補足はごめんこうむりたいです。 質問時に、前提条件は全部書くのが筋ではないでしょうか。
- muturajcp
- ベストアンサー率78% (505/644)
5x=7(mod11) 3x=5(mod19) x=(11*4+1)x=9*5x=9*7=11*5+8=8(mod11) x=(19*2+1)x=13*3x=13*5=19*3+8=8(mod19) 19*11=209だから ∴ x=8(mod(209))
関連するQ&A
- 連立合同式の初級です。急いでいます。
連立合同式の初級です。急いでいます。 問題は… x≡8（mod13），x≡17（mod19） の時です。 答えは… x≡112（mod247） です。お願いしますm(__)m
- ベストアンサー
- 数学・算数
- 連立合同式の商の定理について
連立合同式の商の定理について教えてください。 x,yを整数 m,aを自然数とするとき ax≡ay (mod m) ⇔ x≡y ( mod m/GCD(m,a) ) (おかしな表記ですみません。( mod -)は分数式です) が「商の定理」と習いましたが、これは連立合同式 x≡a (mod K) x≡b (mod L) x≡c (mod M) のK L M が「互いに素」ではないときに適用できる定理だと思うのですが、うまく理解できません。 解らない点:(1) 連立合同式 x≡a (mod K) x≡b (mod L) の時、K L のGCDが「1」で「互いに素」と覚えていますが x≡a (mod K) x≡b (mod L) x≡c (mod M) の時も K L MのGCDが「1」で「互いに素」、それ以上ならば「互いに素」ではないと理解してよいのでしょうか？ 解らない点:(2) x≡a (mod K) x≡b (mod L) x≡c (mod M) で K L M が「互いに素」ではない場合、商の定理を適用した解法でx≡y ( mod m/GCD(m,a) )を求める方法。 K L M が「互いに素」ではない時、K L Mの最小公倍数を使えばよいのは解るのですが、GCD(m,a)の「a」が理解できません。「m」はK L Mの最小公倍数だと思うのですが、「a」は何になるのでしょう？ x≡2 (mod 4) x≡4 (mod 12) x≡3 (mod 9) の場合を例として、具体的に解法を教えてください。 よろしくお願いします。もしも上式が連立合同式として成立しないのであれば、その理由も教えてください。 中国式余剰定理では、( mod ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。 具体的な解法で、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 連立合同式の解法について
連立合同式の解法について具体的に教えてください。 合同式が２つの場合 N≡1(mod2) N≡2(mod3) N≡5(mod2) N≡5(mod3) N-5≡0 (mod2) N-5≡0 (mod3) N-5≡0 (mod6) N=5+6K という形式の解法を習っているのですが、 合同式が３つ、例えば N≡2(mod3) N≡3(mod5) N≡2(mod7) の時、２つの時と同じく右辺を等しくして解を導き出す方法があるのでしょうか？右辺を等しくする方法があれば、具体的に教えてください。よろしくお願いします。
- 締切済み
- 数学・算数
- 合同式の証明
5^2^x≡1{mod2^(x+2)},≡/［合同でない］1{mod2^(x+3)} であることをxに関する数学的帰納法で示しなさい。なおxは自然数とする。 m=1のとき 略 成り立つ m=kのとき与式が成り立つと仮定すると、 5^2^k≡1{mod 2^(k+2)},≡/［合同でない］1{mod2^(k+3)} これを等式で書くと最初の式から5^2^k=2^(k+2)・t+1 (tは整数) m=k+1のとき 5^2^(k+1)={2^(k+2)・t+1}^2=2^(k+3)・t{2^(k+1)・t+1}+1 と示してきたのですが、等式を5^2^k=2^(k+2)・t+1 (tは整数) として後の式を考えると、このtは何と言えるのでしょうか？ これがわからなくて困っています。どなたかアドバイスください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 合同式の解き方を教えてください。
解き方が別の合同式だと思うのですが、それぞれの問題の解き方を教えてください。 一つ目 次の合同式を解く、または、解けないことを証明せよ。 (a) 3x^2 - 5x + 7 ≡ 0 (mod 13) (b) 5x^2 - 6x + 2 ≡ 0 (mod 13) (c) x^2 + 7x + 10 ≡ 0 (mod 11) 二つ目 29の原始根は2であり、指数表を作り、それを使って合同式を解け。 (d) 17x^2 - 3x + 10 ≡ 0 (mod 29) (e) x^7 ≡ 17 (mod 29) これらの問題の解き方を教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
回答ありがとうございます。 申し訳ございませんが、中国の剰余定理を使って解くのです。 よろしかったらもう少し説明をいただけないでしょうか？