- ベストアンサー
合同方程式の解
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
重箱の隅をつつく修正 命題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)
- 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だけ補足に
- graphaffine
- ベストアンサー率23% (55/232)
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個の解を持つことを言えば良い（解があれば、それが±１でないことは明らか) がそれは次の定理から言える。 定理 奇素数ｐに対し、（B)が解を持つためには、p≡1(mod 4)であることが必要十分である。 注：定理では解の個数については言及していませんが、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) で有ることを補足に
- 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
補足
回答ありがとうございます。 ところで、フェルマーの定理は 「ｐが素数なら、a^p≡a(mod p)」 というものですよね？ この定理からどうして回答のような結果が導けるのか がどうしてもわかりません。 申し訳ないですが、補足をお願いします。
関連するQ&A
- modの計算で解が負になることはあるのですか？
modの計算で解が負の数になることはあるのでしょうか？ たとえば，6x≡8 (mod 14) の解は，「-1」と「6」という答え方は正しいのでしょうか？ 「6」と「13」だと思うのですが。 また，この問題の解の個数は2個でしょうか？ もしあっているとするなら，(6, 14) = 2 になるので，2個という考え方であっていますか？ よろしくお願いします。
- 締切済み
- 数学・算数
- 連立1次合同式の解き方がよくわかりません。
連立1次合同式の解き方がよくわかりません。 整数xの連立１次合同式を解きなさい。 5x ≡ 7 (mod11) 3x ≡ 5 (mod19) という問題です。 途中式と答えを教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- 大学数学で、合同方程式の問題なんですが、
大学数学で、合同方程式の問題なんですが、 ｘ＾９７≡２２ ｍｏｄ ２２５ の解の求め方がわかりません。 どなたかおしえていただけないでしょうか それとｘ＾ｔ≡ａ ｍｏｄ ｎ の解を求める際に ｇｃｄ（ａ，ｍ）＝１ ｇｃｄ（ｋ、φ（ｍ））＝１を使うらしいのですが意味がわかりません。 このときのａ，ｍ，ｋは一般自然数です ｘ＾９７は指数でｘの９７乗のことです よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 二次合同方程式の解法過程について
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)
- 締切済み
- 数学・算数
- 最大公約数 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) を導けばよいのでしょうか？ お願いします。
- 締切済み
- 数学・算数
- 合同式
以前も合同式について質問したのですが混乱してしまったのでまた教えてください すいません ２桁の自然数でその２乗した数の下２桁がもとの２桁の自然数に一致するものがある。 このような２桁の自然数を求める問題で ２桁の自然数10x＋yとおくと ２乗すると (10x＋y)＾2=100(x＾2)＋10・2xy＋y＾2 となって y=1のとき(y＾2)=1 y=5のとき(y＾2)=25 Y=6のとき(y＾2)=36 (i)y=1のとき なぜ2x≡x(mod10) x≡0（mod10) になるのでしょうか？ (ii) y=5のとき なぜ 2xy＋2=10x＋2≡2(mod10)となるのですか？ (iii) なぜ 2xy＋2=12x＋2≡2(mod10)と表されるのでしょうか？ そして、 2x＋3≡x(mod10) x＋3≡(mod10) はどこから現れたのですか？ そして、x=7ということはどこからでるのですか？ 質問ばかりですいません 合同式は基礎しかわかりません 例えば５で割って割りきれる数を合同で表すと 0≡5≡10≡15≡(mod5) 私はこのぐらいしかわかりません お願いします
- 締切済み
- 数学・算数
お礼
何度も答えてくださり、ありがとうございました。 整数論が苦手でとても困っていたので助かりました！ 本当にありがとうございます！