• ベストアンサー
  • すぐに回答を!

合同方程式の解

整数論に関する問題です。 pを4|p-1 を満たす素数とする。 このとき x^4≡1(mod p) には法pで 4つの解があることを示せ。 4|p-1とは4がp-1を割り切るという ことです。 解の数とはpを法として互いに合同でないもの の個数のことです。 整数論が苦手で、どうしてもわかりません。 どなたかよろしくお願いします。

共感・応援の気持ちを伝えよう!

  • 回答数5
  • 閲覧数428
  • ありがとう数3

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

  • ベストアンサー
  • 回答No.5
  • keyguy
  • ベストアンサー率28% (135/469)

重箱の隅をつつく修正 命題1: pを素数としP={0,1,2,・・・,p-1}とし nを自然数としf(x)を最高次係数を1とするn次多項式としたとき f(x)≡0 (mod p)を満たすxはPにおいて高々n個しかない 命題2: pを素数としP={0,1,2,・・・,p-1}とし n,kを自然数としf(x),g(x)をそれぞれ最高次係数を1とするn次多項式,k次多項式としたとき f(x)・g(x)≡0 (mod p) のPにおける解のセットと f(x)≡0 (mod p) または g(x)≡0 (mod p) のPにおける解のセットは同じである 問題 pを素数としP={0,1,2,・・・,p-1}とし mをm|p-1を満たす自然数としたとき x^m-1≡0 (mod p)を満たすxはPにおいてm個有ることを示せ 回答 m|p-1よりh(x)を最高次係数1の(p-1-m)次多項式として x^(p-1)-1=h(x)・(x^m-1) とおける ところでフェルマーの定理により x^(p-1)-1≡0 (mod p) はPにおいてp-1個の解を持つから h(x)≡0 (mod p) はPにおいて(p-1-m)個の解を持ち x^m-1≡0 (mod p) はPにおいてm個の解を持つ 命題2は自明なので命題1だけ補足に

共感・感謝の気持ちを伝えよう!

質問者からのお礼

何度も答えてくださり、ありがとうございました。 整数論が苦手でとても困っていたので助かりました! 本当にありがとうございます!

その他の回答 (4)

  • 回答No.4
  • keyguy
  • ベストアンサー率28% (135/469)

最高次係数を1とするが書けていた 命題1: pを素数としnを自然数としf(x)を最高次係数を1とするn次多項式としたとき f(x)≡0 (mod p)を満たすxは0≦x<pにおいて高々n個しかない 命題2: pを素数としn,kを自然数としf(x),g(x)をそれぞれ最高次係数を1とするn次多項式,k次多項式としたとき f(x)・g(x)≡0 (mod p) の解のセットと f(x)≡0 (mod p) または g(x)≡0 (mod p) の解のセットは同じである 問題 pを素数としmをm|p-1を満たす自然数としたとき x^m-1≡0 (mod p)を満たすxは0≦x<pにおいてm個有ることを示せ 回答 m|p-1よりh(x)を最高次係数1の(p-1-m)次多項式として x^(p-1)-1=h(x)・(x^m-1) とおける ところでフェルマーの定理により x^(p-1)-1≡0 (mod p)は0<x<pにおいてp-1個の解を持つから h(x)≡0 (mod p)は0<x<pにおいて(p-1-m)個の解を持ち x^m-1≡0 (mod p)は0<x<pにおいてm個の解を持つ 命題2は自明なので命題1だけ補足に

共感・感謝の気持ちを伝えよう!

  • 回答No.3

bulgarianさん、今晩は。平方剰余の定理を持ち出すのは 反則ですか。 とりあえず、参考程度に。 x^4-1≡0(mod p)----(A)の左辺を因数分解すると、 (x+1)(x-1)(x^2+1)となるから x=1,-1は(A)の解。従って、x^2+1≡0(mod p)----(B)が2個の解を持つことを言えば良い(解があれば、それが±1でないことは明らか) がそれは次の定理から言える。 定理 奇素数pに対し、(B)が解を持つためには、p≡1(mod 4)であることが必要十分である。 注:定理では解の個数については言及していませんが、2個ある事はすぐ分かりますよね。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

「平方剰余の定理」というのは知りませんでしたが、 大変参考になりました。 ありがとうございました!

  • 回答No.2
  • keyguy
  • ベストアンサー率28% (135/469)

sをp未満の自然数としたときX^(p-1)-1をX-sでわった商のp-2次多項式をg(X)としあまりをrすると X^(p-1)-1=(X-s)・g(X)+r X=sとするとフェルマーの定理よりp|rでなけれなならない事がわかるから X^(p-1)-1≡(X-s)・g(X) (mod p) sは1,2,3,・・・,p-1とできるから X^(p-1)-1≡(X-1)・(X-2)・(X-3)・・・(X-(p-1)) (mod p) 注) 0<a<b<pのとき f(x)≡g(x)・(x-a) (mod p) かつ f(x)≡h(x)・(x-b) (mod p) ならば f(x)≡i(x)・(x-a)・(x-b) (mod p) で有ることを補足に

共感・感謝の気持ちを伝えよう!

  • 回答No.1
  • keyguy
  • ベストアンサー率28% (135/469)

フェルマーの定理より X^(p-1)-1≡(X-1)・(X-2)・(X-3)・・・(X-(p-1)) (mod p) 4|p-1より X^4-1|X^(p-1)-1 以上から X^4-1≡(X-a)・(X-b)・(X-c)・(X-d) (mod p) ただし0<a<b<c<d<p

共感・感謝の気持ちを伝えよう!

質問者からの補足

回答ありがとうございます。 ところで、フェルマーの定理は 「pが素数なら、a^p≡a(mod p)」 というものですよね? この定理からどうして回答のような結果が導けるのか がどうしてもわかりません。 申し訳ないですが、補足をお願いします。

関連するQ&A

  • 合同

    整数a,bに対し、差a-bが正の整数nで割り切れる時、a,とbはnを法として合同であるという。 30を法として(2^30)と合同である整数のうち最小値の正の整数を求める問題 (2^30)-n=30N (20^30)=m(mod30)の2つの表した方が分かりません。 (2^30) =(2^5)^6 =(32)^6 =(30+2)^6 から 30K+64とさらに計算して30(K+2)+4になることが分かりません。

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

  • 合同について

    合同の定義は 整数aとbの差がmの倍数であるとき、aとbはmを法として合同 整数aとbをある整数mで割った時の余りが等しいとき、aとbはmを法として合同 このように二つありますが 実際に 4を3で割ると1余る 7を3で割ると1余る 10を3で割ると1余る そして10-7=3 7-4=3 10-4=6 と全て3の倍数になる。 となるというのはわかるのですが なぜ 整数aとbの差がmの倍数であるとき、mで割ったaとbの余りが同じになるのでしょうか。 そうなるものだから、と考えるしかないのでしょうか。 なぜうまい具合にそうなるのか理解できず、すっきりしません。 よろしくお願いします。

  • 連立1次合同方程式

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

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

    大学数学で、合同方程式の問題なんですが、 x^97≡22 mod 225 の解の求め方がわかりません。 どなたかおしえていただけないでしょうか それとx^t≡a mod n の解を求める際に gcd(a,m)=1 gcd(k、φ(m))=1を使うらしいのですが意味がわかりません。 このときのa,m,kは一般自然数です x^97は指数でxの97乗のことです よろしくお願いいたします。

  • modの計算で解が負になることはあるのですか?

    modの計算で解が負の数になることはあるのでしょうか? たとえば,6x≡8 (mod 14) の解は,「-1」と「6」という答え方は正しいのでしょうか? 「6」と「13」だと思うのですが。 また,この問題の解の個数は2個でしょうか? もしあっているとするなら,(6, 14) = 2 になるので,2個という考え方であっていますか? よろしくお願いします。

  • 合同式について

    k(2k^2+1)が3の倍数であることを示すために 3を法とする合同式でkを3通りに分ける問題なのですが kが3の倍数、すなわちk≡0 (mod 3)のとき k(2k^2+1) ≡ 0(2×0^2+1) ≡ 0 (mod 3) kが3で割って1余る数、すなわちk≡1 (mod 3)のとき k(2k^2+1) ≡ 1(2×1^2+1) ≡ 3 ≡ 0 (mod 3) kが3で割って2余る数、すなわちk≡2 (mod 3)のとき k(2k^2+1) ≡ 2(2×2^2+1) ≡ 18 ≡ 0 (mod 3) となると参考書に書かれているのですが この意味がよくわかりません。 k(2k^2+1)が3の倍数であることを示すためには、k( )のkの部分が3の倍数であれば k( )全体が3の倍数になるのでkが3の倍数であることがいえればいいというのはわかるのですが 例えば kが3の倍数、すなわちk≡0 (mod 3)のとき k(2k^2+1) ≡ 0(2×0^2+1) ≡ 0 (mod 3) これは3で割った時にkと0の余りが同じとき という意味だと思うのですが なぜその時に 0(2×0^2+1) このように表現するのかわかりません。 数Aの問題で数学があまり得意ではないので簡単に説明していただけると助かります。

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

    Mr_Holland さんが以前回答された過程で、 「x≡±1 (mod 3)・・・・(1) ∴x=3n±1」・・・・・・(2) と 「±2n≡2 (mod 3)・・・・(3)  この合同式は ±n=1 のとき成立するので・・・(4)  ±n=3m+1 (m:整数)とおける。」・・・・・(5) の2つの展開が異なっているのが、よくわかりませんのでご教授願います。 【補足】 前者は展開が納得できるのですが、 後者は、 ±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)

  • 解の個数

    解の個数 2x+3y=97の非負の整数解(x,y)はいくつ存在するか? 式を変形して y=-2/3x+97/3 97がおそらく素数なので、x,yが何の倍数になればなればよいのか分かりません。 (そもそも解のしぼり方も倍数から判定するのかも分かりません) 「グラフの形からx=1,2,3,,,48まで代入して調べる」以外の方法がありましたら教えてください。

  • modを使用した平方根の求め方

    解き方が解からない問題があります。 どれだけ考えても解き方がわからないので、どなたかわかる方教えてください。 【解き方が解からない問題】 大きな素数の積n=pqが与えられた時、nを素因数分解するのは非常に難しい。 整数mと整数y(<m)が与えられた時y=x2(xの二乗) mod mなる整数解xが存在すれば、yは mod mで平方剰余であるという。 xを mod mでのyの平方根という。 mが素数7の時、 12(1の二乗の事です。二乗の書き方がわからなくて・・・)≡1 (mod 7) 、 22(2の二乗) ≡ 4 (mod 7) 32(3の二乗)≡2 (mod 7) 、 42(4の二乗) ≡ 2 (mod 7) 52(5の二乗)≡4 (mod 7) 、 62(6の二乗) ≡ 1 (mod 7) となるので、1、2、4が平方剰余で、各平方剰余には2個の平方根がある。 mが二つの素数の積の場合、4個の平方根がある。 ここまでが参考書に載ってる説明です。 ここから私がわからない問題です。 102(10の二乗) mod 77=23 n = 77 の素因数7と11から素因数の知識を利用してZのmod nでの平方根Sを計算する。 S2(Sの二乗) ≡ 23 mod 7 S2(Sの二乗) ≡ 23 mod 11 上の2つを解いて、mod 77での4つの平方根10、32、45、67を得る。 この2つの式から、何をどうやって計算して、4つの平方根10、32、45、67が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。