• ベストアンサー

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

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

質問者が選んだベストアンサー

  • ベストアンサー
  • proto
  • ベストアンサー率47% (366/775)
回答No.1

まず法225に対してφ(225)を求めます。 (φ(x)はオイラー関数) 　　225 = (3^2)*(5^2) より 　　φ(225) = φ(3^2)*φ(5^2) = (3^2-3)*(5^2-5) = 120 次に 　　gcd(97,φ(225)) = gcd(97,120) = 1 であることを確かめます。 実際これは成り立ちますね。自身で確かめて見てください。 gcd(97,120)=1より 　　97x+120y = 1 を満たす整数x,yが存在します。 そのようなx,yのうちyが負である組を何でも良いので一つ見つけます。 (ユークリッドの互除法の逆などで求めれば良いでしょう) 今回はそのようなx,yのうちx=73,y=-59を取ります。 (別のx,yでも解けます) x,yを元の式に代入すると 　　97*73-120*59 = 1 　　97*73 = 1+120*59 となります。 これを用います。 　　x^97 ≡ 22　　(mod 225) 両辺を73乗すると 　　(x^97)^73 ≡ 22^73 　　x^(97*73) ≡ 22^73　　(mod 225) 97*73=1+120*59より 　　x^(1+120*59) ≡ 22^73 　　x * (x^120)^59 ≡ 22^73　　(mod 225) さて、オイラーの定理より 225と互いに素なxについて 　　x^φ(225) = x^120 ≡ 1　　(mod 225) が成り立つから、 　　x * (x^120)^59 ≡ x * 1^59　≡ 22^73 　　x ≡ 22^73　　(mod 225) 以上より22^73(mod225)が答え。 あとは計算。

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

関連するQ&A

  • 連立１次合同方程式

    連立１次合同方程式 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 これをどのように示したらよいか分かりません。 １次合同方程式を解くことはできるのですが、証明となるとどうしていいか分からなくなってしまいました。 分かる方、助けてください。

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

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

  • 合同式の証明

    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は何と言えるのでしょうか？ これがわからなくて困っています。どなたかアドバイスください。 よろしくお願いします。

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

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

  • 最大公約数 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) を導けばよいのでしょうか？ お願いします。

  • 合同式の証明

    5^2^x≡1{mod2^(x+2)},≡/［合同でない］1{mod2^(x+3)} であることをxに関する数学的帰納法で示しなさい。なおxは自然数とする。 x=1のとき　略　成り立つ x=kのとき与式が成り立つと仮定すると、 5^2^k≡1{mod 2^(k+2)},≡/［合同でない］1{mod2^(k+3)} これを等式で書くと最初の式から5^2^k=2^(k+2)・t+1 (tは奇数) tは奇数ということからこの後どのように証明していけばいいのでしょうか？ 行き詰っています、どなたかアドバイスください。お願いします。

  • 至急。数学の問題を教えてください。

    数学の問題で、どうしてもわからない問題があるので、教えていただければと思います。 ４つあるので、どれか1つだけでもかまいません。途中式を書いていただければなおうれしいです。 １、 √２０ ━━ ｎ が自然数となるような、最も小さい自然数 ｎ の値を求めなさい。 √３ ２、 2次方程式 X2乗＋３X ー 4分の3（a＋３）＝０の解が1つしかなくなるような、aの値を求めなさい。また、その時の解を求めなさい。 ３、 十の位の数と一の位の数の和が6である2ケタの自然数がある。この自然数は、十の位の数と一の位の数の積より４６大きい。十の位をXとして、次の問いに答えなさい。 この2ケタの自然数の位置の位の数をXを用いた式で表しなさい。 なお、この十の位の数と一の位の数が和が6となり、積が46大きい2ケタの自然数は５１だとわかっています。 ４、2次方程式の解の公式　X＝2分のーｂ±√ｂ2乗ー４acを利用して　３X2乗-3X-2=0の解を次のように求めました。空欄を埋めなさい。 両辺に3倍すると　９X2乗-(１)X－(２)＝０ (３)をMとすると　M2乗ー(４)M－(５)＝０ これを上の公式を用いて解くとM＝(６) したがって、X＝(７)となり、解を求めることができる。　(３)～(７)を教えてください。１，２はそれぞれ9，6と分かりました。 なお、ヒントを出す形やサイトのURLを張って行くだけでもかまいません。 11日連続で休んでしまったためこの部分の授業が全部できなかった為、教科書を読んだり、調べたりしてもぜんぜんわかりません でした。 先生に聞いてもわかりやすく教えてくれず、とても困りました。お願いします。

  • 合同式の問題

    (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)の合同式を解きたいのですが解法がわかりません。教えてください。

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

    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)

  • 数学の方程式の分野の問題で質問があります

    数学の問題で質問があります。 ２次方程式 Xの2乗-X-1＝0の2つの解をα、βとおく。 3次方程式X３乗+ａX2乗+bX+1＝0 がα、βを解にもつとき、係数a,bの値を求めよ。 また、この3次方程式のもうひとつの解を求めよ。 途中式、答えまで書いていただけるととても助かります。 よろしくお願いします

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する