• 締切済み

合同式の解き方

合同式の解き方と一口に言っても色々な物があるとは思うのですが、私は現在以下の合同式が解けないで困っています。 x^329≡452(mod1147) フェルマーの小定理を使って解くのだとは思うのですが、如何せんmodが1147と大きすぎるためにうまく処理することができません。 答えをそのまま聞くのはあまりにもおこがましいので、よろしければヒントだけでも教えて頂けないでしょうか。 よろしくお願いします。

みんなの回答

  • rabbit_cat
  • ベストアンサー率40% (829/2062)
回答No.4

x^329 ≡ 452 (mod 1147) の両辺をn乗すると、 (x^329)^n = x^329n ≡452^n (mod 1147) ところで、オイラーの定理より x^1080 ≡ 1 (mod1147) です。 ここで、 329n ≡ 1 (mod 1080) となるような整数nを探します。（１次合同方程式） 329と1080は互いに素なので解が存在します。 適当にユークリッド互助法などを利用して解を探すと、 n ≡ 929 (mod 1080) です。 というわけで、 (x^329)^929 ≡ x ≡452^929 (mod 1147) です。一応解けました。 452^929(mod 1147)を実際に計算するのは（大変は大変だけど）まあ、手計算でもできなくはないレベルでしょう。 1147 = 31*37 を使うと、452^929(mod 1147) の計算をちょっとだけ簡単にできますが。

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.3

や, 法が素数じゃないと「Fermat の定理」は使えないし. だから法が素数かどうかでわざわざ分けたんだけどねぇ. もちろん CRT (Chinese Reminder Theorem) でもいいんだけど, どのように使うつもりでいますか?

  • kup3kup3
  • ベストアンサー率68% (33/48)
回答No.2

今晩は。 34×34＝1156で1147を越えるが一番近い数である。 だから素数かどうかは、31までの素数で1147を割って行けば すぐ分かるよ.(^^);

harukako15
質問者

お礼

回答ありがとうございます。 申し訳ございませんが、問題との関連性がいまいちわかりません。 よろしかったらもう少し説明をいただけないでしょうか？

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.1

1147 が素数なら Fermat の定理を使うことになるし, 素数でなければ... Euler の定理だっけ? x^φ(n) ≡ 1 (mod n) を使うことになるかな.

harukako15
質問者

お礼

回答ありがとうございます。 オイラーの定理を使うという考えもあったのですが、どうもうまく解くことができません。 中国式剰余定理を使うという手段も思いついたのですが、いかがでしょうか？

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

関連するQ&A

  • 【至急】お願いします。合同式に関して

    中学二年なんですが、合同式に関して質問があります。 41の2006乗を43で割った余りは? という問題なのですが、解答を見ますと、 フェルマーの小定理より、 　41の42乗≡1 (mod43) ∴41の2006乗≡(41の42乗)の47乗×41の32乗 　　　　　　≡-2の32乗 　　　　　　≡2の32乗 (mod43)　 　　 ここまではわかります。ただその後の、 ここで、2の8乗≡16の2乗≡-2 (mod43) より、 　41の2006乗≡-2の4乗≡16 (mod43) よって求める余りは16 までがわからないのです。 特に、「2の8乗≡16の2乗≡-2 (mod43) より、」というのがまったくわからないのです。 私の数学の先生はどうも天才肌のようで、私が聞いてもよくわからないのです。 どなたかわかりやすく説明していただけますでしょうか。至急でお願いします。

  • 連立1次合同式の解き方がよくわかりません。

    連立1次合同式の解き方がよくわかりません。 整数xの連立１次合同式を解きなさい。 5x ≡ 7 (mod11) 3x ≡ 5 (mod19) という問題です。 途中式と答えを教えてください。 よろしくお願いします。

  • 連立合同式

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

  • 連立合同式の初級です。急いでいます。

    連立合同式の初級です。急いでいます。 問題は… x≡8（mod13），x≡17（mod19） の時です。 答えは… x≡112（mod247） です。お願いしますm(__)m

  • 参考となる図書の推薦をお願いします。

    風変わりな質問になることをお詫びします。 次にあげる1～4の問題が解けるようになりたいのですが、 参考となる図書の推薦をしていただけないでしょうか？ よろしくお願いします。 1.　フェルマーの定理を述べよ. 2.　フェルマーの定理を利用して,1^30+2^30+3^30+・・・+10^30≡-1(mod 11)を示せ. 3.　11x≡10(mod 15)を解け. 4.　7x≡8(mod 16)を解け.

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

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

  • 連立合同式の解法

    連立合同式 x≡5(mod 16), x≡15(mod 22) の数学的解法がわかりません。中国剰余定理は知っていますが、16と22は互いに素でないので、他の解法が存在するのでしょうか。 または、互いに素の場合でも使用できる中国剰余定理の拡張が存在するのでしょうか。 適当な整数を代入して試す方法（総当たり法）はなしでお願いします。

  • フェルマーの定理の公式の解き方について

    秘密鍵と公開鍵について勉強していますが、フェルマーの定理が使われていると聞いたのですが、このフェルマーの定理というのは大学とかで習うものなのでしょうか？x ≡ 0 (mod p) でなければ x^(p-1) ≡ 1 (mod p) という式をみても計算方法がよくわからず困っています。よくわかる参考書等をご存知の方がいらっしゃればご教授お願いします。

  • 合同式

    (1)43x+56y=10を満たす整数x,yを求めよ。 (2)あるイベントで1ケース24本入りの缶を何ケースか開けて、1人7本ずつ分けたところ、1本残った。参加予定人数は25人であるとすると、参加したのは何人か。 という問題なのですが、 (1)43x=-56y+10 43x≡10(mod 56) (2)ケースの数をx、参加した人数をyとすると、 24x=7y+1…(1) 24x≡7y+1(mod 7) 24x≡6(mod 7) 4x≡1(mod 7) gcd(4,7)=1 x=5 (1)に代入して、y=17 よって、答えは17人。 (1)は、この後の計算の仕方はネットでも調べてみたのですが、いまいち、分からず困っています。(2)の方は、この計算方法で合っているでしょうか？他にもやり方はあるんでしょうか？ アドバイスやヒントなど、よろしくお願いします。

  • 二次合同方程式の解法過程について

    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)

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する