• 締切済み

ユークリッド互除で合同式の問題を解く

学校の課題でわからなかった所です。 mを法としてaとxが合同である、という問題を解いています。ax (三本線)b（mod m） という合同式です。 ax-my=b=gcd(a,m)に直してｘを求めてます。 ｘが二乗になった時の解き方がわかりません。 わかりにくい質問ですみませんがお願いします。

みんなの回答

  • yaksa
  • ベストアンサー率42% (84/197)
回答No.1

2次合同式 ax^2 ≡ b (mod m) を解けということですか。 ここで説明するのは大変なんで、キーワードを「」でくくっておくので、google等で検索してください。けっこう、有益な情報がたくさんみつかると思います。 とりあえず、x^2について1次合同式だと思って解くと x^2 ≡ c (mod m) になります。これを解けばいいんですが、 まず、法mが素数でないと厄介なんで、 「中国剰余定理」（「中国人剰余定理」） を使って法が素数の合同式に分解します。 で、 x^2 = a (mod p) の形を2次合同式を解くには、 「平方剰余」「平方非剰余」「ルジャンドルの記号」 といった概念が必要になるので、検索してください。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ユークリッドの互除法についての問題です。

    ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき　ax≡b (mod5) (2)aが4の倍数でないとき　ax≡b (mod4) 誰か教えてください。

  • 大学数学で、合同方程式の問題なんですが、

    大学数学で、合同方程式の問題なんですが、 ｘ＾９７≡２２　ｍｏｄ　２２５ の解の求め方がわかりません。 どなたかおしえていただけないでしょうか それとｘ＾ｔ≡ａ　ｍｏｄ　ｎ の解を求める際に ｇｃｄ（ａ，ｍ）＝１ ｇｃｄ（ｋ、φ（ｍ））＝１を使うらしいのですが意味がわかりません。 このときのａ，ｍ，ｋは一般自然数です ｘ＾９７は指数でｘの９７乗のことです よろしくお願いいたします。

  • ユークリッドの互除法

    ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。

  • 連立１次合同方程式

    連立１次合同方程式 x≡b_1(mod m) x≡b_2(mod n) の一般解をxとするとき、gcd(m,b_1)=1かつgcd(n,b_2)=1であるならば、かつその時に限り、gcd(mn,x)=1 これをどのように示したらよいか分かりません。 １次合同方程式を解くことはできるのですが、証明となるとどうしていいか分からなくなってしまいました。 分かる方、助けてください。

  • 拡張ユークリッド互除法による乗法逆元の求め方

    こんにちは。 タイトルの通りの質問なのですが、過去ログを参考にしても特別分からないところがあったため、質問させて下さい。 11^-1 ≡ x(mod 31) このxを求めたいのですが、11x * 31y = gcd(11, 31)として解いたら、 -14 * 11 + 5 * 31 = 1 となってしまい、うまくいきません。 以下、自分なりの解法です。 ----------------------------------------------------- 11^-1 ≡ x(mod 31)より、11x ≡ 1(mod31) これは、11x + 31y = 1を示す。 gcd(11, 31)　　　11 = a, 31 = b とする = gcd(31, 11)　　　→ b = 2a + 9 　　　　　　→ 9 = -2a + b = gcd(11, 9)　　　　→ a = (-2a + b) + 2 　　→ 2 = 3a - b = gcd(9, 2) 　　　　→ -2a + b = 4(3a - b) + 1　―(1) = gcd(2, 1) = gcd(1, 0) = 1 (1)の式より、-14a + 5b = 1 先ほどの式と照らし合わせて、(x, y) = (-14, 5) したがって、11^-1 ≡ -14(mod 31) ----------------------------------------------------- おそらく、11x > 31yの条件が取り入れられてないのが原因だと思いますが、どう使えばいいかわからないです。 どなたか正しい解法を教えてください。 よろしくお願いします。

  • 連立合同式の商の定理について

    連立合同式の商の定理について教えてください。 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 ○ )が「互いに素」ではない場合にも解を求める事ができると、参考書にはあるのですが、最小公倍数を使う事しか理解できません。 具体的な解法で、よろしくお願いします。

  • 拡張ユークリッド互除法について

    大学で習ったのですが、いまいちピンとこないので教えてください。 例えば ax = 1 mod n みたいな場合、xがaの逆元になるのでしょうが、逆元を持つ条件として gcd(a,n)=1である必要があると思います。 法nがn=pq（p,qは素数）みたいな合成数でも、逆元はある時はありますよね？ aとnが互いに素であればいいのだから… それとも法は素数じゃないとダメなんでしょうか？ 私の解釈は間違ってますか？

  • 最大公約数 gcd(a,b,c)　と一次合同式の解の存在

    初等整数の証明で困ってます。 (1)gcd(a,b,c)はgcd(a,b)の約数であることを証明せよ。 (2)gcd(gcd(a,b),c)はgcd(a,b,c)の倍数であることを証明せよ。 また合同式の定理の証明について gcd(a,b)=1ならばax≡c(mod b)は解をもつ。 さらにこの合同方程式の一つの解をpとすると、すべての整数kについてp+kb も解である。逆にこの合同方程式の任意の解はp+kb　と表わされる。 ax≡c(mod b)　は b | (ax-b) を導けばよいのでしょうか？ お願いします。

  • 合同式の問題

    (1)3x≡1(mod 5) (2)9x≡6(mod 15) (3)C'a={x|x≡a(mod m)},Ca={x|x≡a(mod n)}とする。nがmの約数とすれば、C'a ( Caであることを示す方法と(1)(2)の合同式を解きたいのですが解法がわかりません。教えてください。

  • ユークリッドの互除法について

    教科書に書いている証明がわからないので質問します。 f(x)=x^3+Ax+Bをf'(x)=3x^2+Aで割った余りを求めると(2A/3)x+Bであり 、f(x)とf'(x)がたがいに素でないのならf'(x)が余り(2A/3)x+Bで割り切れる必要があると書いているのですが、これはなぜでしょうか。 わかる人がいれば教えてください。よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する