- ベストアンサー
連立合同式の解法
連立合同式 x≡5(mod 16), x≡15(mod 22) の数学的解法がわかりません。中国剰余定理は知っていますが、16と22は互いに素でないので、他の解法が存在するのでしょうか。 または、互いに素の場合でも使用できる中国剰余定理の拡張が存在するのでしょうか。 適当な整数を代入して試す方法（総当たり法）はなしでお願いします。
- 数学・算数
- 回答数1
- ありがとう数2
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
> 中国剰余定理は知っていますが との仮定で。 取り敢えず、x≡15(mod 22)というのは、 x≡ 1(mod 2)かつ、x≡ 4(mod 11)と等しい、というのはいいでしょう。 とすれば、問題は、 x≡5(mod 16)かつx≡ 1(mod 2)かつx≡ 4(mod 11)と等しい訳ですが、 ところがx≡5(mod 16)ならx≡ 1(mod 2)なので、 結局問題は x≡5(mod 16)かつx≡ 4(mod 11) と同じになり、これなら解けるでしょう。 こんな感じで分割するとよい。
関連するQ&A
- 連立合同式の商の定理について
連立合同式の商の定理について教えてください。 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 ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。 具体的な解法で、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 連立1次合同式の解き方がよくわかりません。
連立1次合同式の解き方がよくわかりません。 整数xの連立１次合同式を解きなさい。 5x ≡ 7 (mod11) 3x ≡ 5 (mod19) という問題です。 途中式と答えを教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- 連立合同式の解法について
連立合同式の解法について具体的に教えてください。 合同式が２つの場合 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) の時、２つの時と同じく右辺を等しくして解を導き出す方法があるのでしょうか？右辺を等しくする方法があれば、具体的に教えてください。よろしくお願いします。
- 締切済み
- 数学・算数
- オイラーの定理(整数)
nは自然数、aは整数とする。aとnが互いに素な時、a^{φ(n)}≡1( mod n)が成り立つ。 ここでφ(n)は「n以下の自然数でnと互いに素なものの個数を表す」"オイラーの関数"である。 この定理の例証で、例えばn=45=3^(2)*5のときa=7として考えます。 φ(45)=φ(3^2)*φ(5)となり、φ(3^2)=6、φ(5)=4です。 フェルマーの小定理よりmod 5 で、7^φ(45)={7^φ(5)}^φ(3^2)は {7^φ(5)}≡1 (mod 5)より、7^φ(45)≡1 (mod 5 )・・・(1)になり。 次に7^φ(3^2)≡1(mod 3^2)をしるします。フェルマーの小定理より mod 3 で 7^(3-1)≡1なので7^(3-1)＝3k+1、 7^φ(3^2)={7^(3-1)}^3＝(3k+1)^3=(3k)^3+3C1(3k)^2+3C2(3k)+1 3C1、3C2は３の倍数なので、7^φ(3^2)≡1(mod 3^2)・・・(2)です。 よって、7^φ(45)={7^φ(3^2)}^φ(5)≡1(mod 3^2)となります。 ここからが分からない箇所なのですが、中国の剰余定理から、 (1)かつ(2)⇔7^φ(45)≡■(mod 3^(2)*5)となる■が、1つだけ存在します。と書いてありますが、自分は中国の剰余定理は、m、nを互いに素な自然数とする。 x≡a(mod m)かつ x≡b(mod n)を満たす整数xはmnを法として、ただ1つ存在する。と書いてあることから、割る数が違えば、a,bのように余りもちがう場合に、整数xはmnを法として、ただ1つ存在する。と思っていたのですが、 この例証では、■≡7^φ(45) (mod 5)かつ■≡7^φ(45) (mod 3^2)のような余りが 一緒の場合を同時に満たす■を求めているような気がして、中国の剰余定理があてはまるか不安です。 自分の考えの間違いや、余りが一緒の場合でも中国の剰余定理が使えるかを教えてください。お願いします。 本では、■＝1のとき(1)、(2)が成り立つので、■＝1だとわかります。 よって7^φ(45)≡1(mod 45 )となることがしるされました。としめくくっています。
- ベストアンサー
- 数学・算数
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,ｑを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-１乗してはじめて１になり、かつ法qにおいてもq-1乗してはじめて１になるわけだと思います。（ほかにも条件がありますが…） で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- 連立合同式の初級です。急いでいます。
連立合同式の初級です。急いでいます。 問題は… x≡8（mod13），x≡17（mod19） の時です。 答えは… x≡112（mod247） です。お願いしますm(__)m
- ベストアンサー
- 数学・算数
- 代数学の、整数の合同の問題を教えて下さい。
この問題がわからず困っています。 (1)n,mは互いに素な整数とする。 このとき、sn+tm=1となる整数s,tが存在する。 a,bを整数とする時、x=bsn+atmとおく。このとき、xは合同式 x≡a mod n x≡b mod m を満たすことを示しなさい。 (2)さらに、xをnmで割った余りをrとする。この時rは r≡a mod n r≡b mod m を満たすことを示しなさい。 という問題です。 分かる方、よろしくお願いいたします
- ベストアンサー
- 数学・算数
- 二次合同方程式の解法過程について
Mr_Holland さんが以前回答された過程で、 「x≡±1 (mod 3)・・・・（１） ∴x=3n±1」・・・・・・（２） と 「±2n≡2 (mod 3)・・・・（３） この合同式は ±n=1 のとき成立するので・・・（４） ±n=3m+1 （m:整数）とおける。」・・・・・（５） の２つの展開が異なっているのが、よくわかりませんのでご教授願います。 【補足】 前者は展開が納得できるのですが、 後者は、 ±n=1(mod 3)から ⇔n=±1(mod 3)と同じだから、 ⇔n=3m±1と展開できるので、 （5）式±n=3m+1と異なります。 後者の妥当性が知りたいです。 以下、Mr_Holland さんからの 回答 2010-11-17 10:57:57 回答No.2 Mr_Holland ANo.1は煩雑でした。 もう少しスマートに計算することができましたので、以下に示します。 x^2≡7 (mod 27) ⇒x^2≡7 (mod 9) ⇒x^2≡1 (mod 3) ⇔x≡±1 (mod 3) ∴x=3n±1 (n:整数）とおける。 以下、複号同順とします。 x^2=(3n±1)^2= 9n^2±6n+1 だから x^2≡±6n+1≡7 (mod 9) ∴±6n≡6 (mod 9) ∴±2n≡2 (mod 3) この合同式は ±n=1 のとき成立するので ±n=3m+1 （m:整数）とおける。 x^2=9(3m+1)^2+6(3m+1)+1 =81m^2+72m+16 だから x^2≡18m+16≡7 (mod 27) ∴18m+9≡0 (mod 27) ∴2m+1≡0 (mod 3) この合同式は m=1 のとき成立するので m=3k+1 （k:整数）とおける。 x=3n±1=±(±3n+1)=±{3(3m+1)+1}=±(9m+4)=±{9(3k+1)+4}=±(27k+13) ∴x≡±13 (mod 27) ∴x≡13,14 (mod 27)
- 締切済み
- 数学・算数
お礼
おかげさまで解決しました。 わかりやすい回答をありがとうございました。