- ベストアンサー
modに関する証明問題
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
aがpで割り切れるとき (a^{(p+1)/4})^2≡0≡a (mod p) だから正しい。 aがpで割り切れないとき x^2≡a (mod p)が解を持つ ⇒ a^{(p-1)/2}≡1 (mod p)・・・・※ が言えます(※がわからなければ、下記のP.S.その1を参照してください)。 したがって、x^2≡a (mod p)が解を持つ時点で、a^{(p-1)/2}≡1 (mod p)が言えます。 以上より (a^{(p+1)/4})^2≡a^{(p+1)/2}≡a^{(p-1)/2}*a≡a (mod p) が言えます。 P.S.その1 ※の説明 pを素数、aをpで割り切れない整数とする。 x^2≡a (mod p)が解を持つとき xがpで割り切れないことを言います。 xがpで割り切れると仮定すると a≡x^2≡0 (mod p)だからaがpで割り切れることになり不合理 よって、xはpで割り切れない。 したがって、フェルマーの小定理(わからなければ、下記のP.S.その2を参照してください)より a^{(p-1)/2}≡(x^2)^{(p-1)/2}≡x^(p-1)≡1 (mod p) が言えます。 P.S.その2 P.S.その1のフェルマーの小定理ですが、以下のようなものです。 pを素数、nをpで割り切れない整数とするとき n^(p-1)≡1 (mod p) が成り立つ 証明は例えば以下のURLを参照してください。
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
a ≡ b^2 (mod p) を使い, a^(p+1)/4 を 2乗して a になることが言えればいいのでは?
お礼
どうもありがとうございます。
関連するQ&A
- 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が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 合同式の問題の証明を教えて下さい。
gcd(b,561)=1であれば b^560≡1(mod 3) b^560≡1(mod 11) b^560≡1(mod 17) が成り立つことを証明せよ。 ヒント: pが素数でbを割り切らなければ b^(p-1)≡(mod p) が成り立つ。 という問題なのですが分かりやすく証明を教えていただけないでしょうか?
- 締切済み
- 数学・算数
- ゼロ知識証明の勉強をしているのですが…
ゼロ知識証明の勉強をしているのですが… 途中で 1.m が合成数の時、m を素因数分解できれば任意の y の mod m での平方根を簡単に求めることができる。逆に任意の y に対する mod m での平方根が求まるならば、m を簡単に素因数分解できる。 2.m を素因数分解できれば、任意の y に対し mod m での平方剰余性を簡単に判定できる。 とあったのですが、計算方法が解らないので、納得が出来ません。 具体的な計算方法が解る方がいらっしゃいましたら、ご教授願います。
- ベストアンサー
- 数学・算数
- 3次方程式の解法(カルダノの公式)
現在、3次方程式をカルダノの方法で解いているのですが、 以下に示すURLにある一文の、 「カルダノの公式を用いると x3 + p x + q = 0 という三次方程式は 式A(何故かコピペできません・・・仮に式Aとします) の時に負の数の平方根が現れる。これは、この方程式の判別式 D = − (4 p3 + 27 q2) > 0 と同値な条件であり 3 つの異なる実数解を持つ条件である。実数解しかないのにも関わらず、カルダノの公式では負の数の平方根を経由する必要がある。カルダノは負の数の平方根を計算に用いることはあったものの、それらの場合は不可能で役に立たないものと考えていた。」 http://ja.wikipedia.org/wiki/%E4%B8%89%E6%AC%A1%E6%96%B9%E7%A8%8B%E5%BC%8F なぜ、式Aでは平方根の中がマイナスになり複素数がでてくるのに、実数解を持つ条件なのか理解できません。 上のD>0と同値な条件というのもなんだか納得いきません。どなたか教えていただけませんか? の意味が理解できません。まず、
- ベストアンサー
- 数学・算数
- √5≡y (mod p )が解を持つための条件は?
素数p に対し、√5≡y (mod p ) を 5≡y^2 (mod p )と定義したとき、√5≡y (mod p )が解を持つための必要十分な条件は p≡±1(mod 5)らしいのですが本当でしょうか?(必要あるいは十分だけ?)正しいときはどのように(あるいはどのような方針で)証明したらいいのでしょうか。また、参考文献があれば教えてください。
- ベストアンサー
- 数学・算数
- おそらく三角比を用いた証明問題
△ABCにおいて∠B=60°、bが整数、c・aが素数の三角形が正三角形になることを示せ。 という問題なのですが、解答の指針が立ちません。 とりあえず考えたところまでを書きます。 「 三角形ABCにおいて b=a cosC +c CosA …(1) となり、0°<C<120°⇔-1/2<cosC<1、cosCは実数より cosC=(α+β√q)/p(pは自然数、qは平方数でない自然数、α、βは整数)と表せる。 」 とおいてそこからsinCをαβpqで表し、A=120°-Cから加法定理を用いてcosAを表して(1)に代入し、bが整数なので√部分がなくなることからβ=0、α/p=1/2を導き出そうと思ったのですが、かなり複雑になるのでもっとあらかじめ絞り込めそうな気も他の解法がある気もします。 ちなみに計算を間違えてなければ(1)式は b={(2a-c)α+(2a-c)β√q+c(3(p^2-(α+β√q)^2))^(1/2)}/2p となり、ここからβ=0かつ後ろの根号部分=0or平方数で式をたてていこうと思ったのですが… このまま続けても答えに辿り着くでしょうか?アドバイスお願いします。
- ベストアンサー
- 数学・算数
- 高木初等整数論 p85
初等整数論で (n/m)は平方剰余のルジャンドルの記号、もしくは,Jacobiの記号とします。水平の-が書けないため。 (記号の説明) φ(m):オイラー関数:mと素である整数の数 Legendreの記号 x^2≡a (mod.p)が解をゆうするときにaをpの平方剰余、そうでないとき平方非剰余という。 not(a≡0) (mod.p)でないとき、aが平方剰余であるか、非剰余であるかに従って (a/p)=+1または-1 (m/n)の定義 n>1が奇数で,n=pp'p''---が、nの素因数分解でsるとき,(m,n)=1なる整数mに関して (m/n)=(m/p)(m/p')(m/p'')---とする。 右辺は、Legendreの記号 jacobiの記号 (定理) mが平方数でないならば、mを法とするφ(m)個の既約類のうち、半数に属するnに対しては(n/m)=+1、他の半数に対しては、(n/m)=-1 (証明)と続きますが。 mを法とする同一既約類に属するnに対しては(n/m)の値は一定. いまφ(m)個の既約類の代表を(n/m)の値によって+の組と-の組とに分けて、 (+) a1、―――,an (a/m)=+1 (-) b1、―――,bn (b/m)=-1 とする。 a≡1(mod m)であるaなどは+の組に属するが、仮定でmは平方数でないから、-の組も空虚でない。 (質問)mは平方数なら、-の組は空虚は明らかですが、mは平方数でないから、-の組も空虚でないはどうしていえるのでしょうか。わかりやすく説明ください。
- 締切済み
- 数学・算数
- 整数の問題なんですが
次の問題が解けません。 「X^2+7≡0 mod p を満たす解のある素数 p>7 を考える。 p mod 14 はいくつか」 手作業でやってみたところ、 1,7,9,11 が出てきましたが、それ以上のことは分かりません。 解き方の分かる方教えてください。
- 締切済み
- 数学・算数
- フェルマーの無限降下法
1973をフェルマーの無限降下法を使って二つの平方数の和に 表せという問題です。 259^2+1^2=34*1973からはじめていき、 21≡259(mod34) 1≡1(mod34) となる数、1と21を選び、 21^2+1^2≡259^2+1^2≡0(mod34) 21^2+1^2=34*13 259^2+1^2=34*1973 と表します。 (21^2+1^2)(259^2+1^2)=34^2*13*1973 恒等式を使い、(u^2+v^2)(a^2+b^2)=(ua+vb)^2+(va-ub)^2 (21*259+1*1)^2+(1*259-21*1)^2=34^2*13*1973 と表せます。 5440^2+238^2=34^2*13*1973 いずれも34で割り切れる。 (5440/34)^2+(238/34)^2=13*1973 160^2+7^2=13*1973 より小さい1973の乗数がえられました。 しかし、ここから無限降下法をつづけても無限にループしてしまい 解にたどり着きません。どうしたら 良いのでしょうか?
- ベストアンサー
- 数学・算数
お礼
分かりやすい回答どうもありがとうございました。