• ベストアンサー
  • 困ってます

modに関する証明問題

pをp≡3mod4を満たす素数として、a≡b^2mod pが解を持つとしたとき a^(p+1)/4 が a の mod p での平方根になる ことを示したいのですが、どうしてそうなるのか、さっぱりです。 どなたか教えていただけないでしょうか。

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

  • 回答数2
  • 閲覧数198
  • ありがとう数5

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

  • ベストアンサー
  • 回答No.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を参照してください。

参考URL:
http://aozoragakuen.sakura.ne.jp/suuronN/node38.html

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

質問者からのお礼

分かりやすい回答どうもありがとうございました。

その他の回答 (1)

  • 回答No.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が導き出せたのかわかりません。 二乗の表記の仕方がわからず、とても見難くなってしまいました。すみません。 乱文になってしまいましたが、どなたかわかる方教えてください。 よろしくお願いします。

  • √5≡y (mod p )が解を持つための条件は?

    素数p に対し、√5≡y (mod p ) を 5≡y^2 (mod p )と定義したとき、√5≡y (mod p )が解を持つための必要十分な条件は p≡±1(mod 5)らしいのですが本当でしょうか?(必要あるいは十分だけ?)正しいときはどのように(あるいはどのような方針で)証明したらいいのでしょうか。また、参考文献があれば教えてください。

  • 数学、mod pのk乗

    xの2乗≡a(mod pのk乗)が整数解を持てばxの2乗≡a(mod pのk+1乗)も整数解を持つ pは素数、kは0以上の整数、aは整数 この証明についての質問です。 xの2乗≡a(mod pのk乗)の整数解をx1とすると x1の2乗-a=(pのk乗)s sは整数 x2=x1+(pのk乗)tとおくと x2の2乗-a=(x1+(pのk乗)t)の2乗-a =x1の2乗+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗)-a =(x1の2乗-a)+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗) =(pのk乗)s+2(x1)(pのk乗)t+((pのk乗)の2乗)(tの2乗) =(pのk乗)(s+2(x1)t+(pのk乗)(tの2乗)) ここまではいいのですが s+2(x1)t≡0(mod p)となるようにtを選ぶことができるというのがわかりません。 ここを通過すればpのk+1乗を約数にもつことになって証明が終わります。

  • ウィルソンの定理の証明は?

    ウィルソンの定理 (n - 1)! + 1≡ 0(mod n) n:素数 の証明が思いつきません。 たとえばn=7とすると、 6!=(6・1)(5・3)(4・2) =6・15・8 のように分解できるようなのですが、 すべての素数についてこのように分 解できることを証明するためには、 どうしたらよいのでしょうか?

  • (mod p)?

    pが素数、a,bがZに含まれるとき、次式を示せ。 a≡b(mod p)⇒a^p^k≡b^p^k(mod p^(k+1))

  • 素数の集合をmod pで分類すると

    素数の集合P={2,3,5,7,11,13,…} に対し、素数pをひとつとります。 p以外の素数をpで割った余りは、 1, 2, …, p - 1 となりますが、それらは同じ程度存在するのでしょうか? つまり、n個の素数の集合を P(n)={2,3,5,7,11,13,…,p_n} (ただし、p_nはn番目の素数) とし、 n→∞のとき、 ♯{q∈P(n)|q≡1 (mod p)}/n → 1/(p-1) ♯{q∈P(n)|q≡2 (mod p)}/n → 1/(p-1) … ♯{q∈P(n)|q≡p-1 (mod p)}/n → 1/(p-1) は成り立つのでしょうか。

  • mod計算について

    nが素数p,qの積からなる合成数のとき、例えば a mod n を考える場合、aはp,qを因数に含みませんよね? つまり、aとnは互いに素? 合ってますでしょうか?

  • 2^10≡1 mod pを満たす素数p

    「2^10≡1 mod pを満たす素数pをすべて求めよ」という問題ですが、 2^10-1=1023=3・11・31より pは3, 11, 31で正しいでしょうか?他にもあるでしょうか? 少し自信がないので質問しました。

  • p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq

    p,qが素数のときn^{(p-1)(q-1)+1}≡n (mod pq)になりますか? nがpともqとも互いに素であるときは、 Fermatの小定理を使えばn^{(p-1)(q-1)}≡1 (mod pq) が言えるので、標記の命題は言えると思うのですが pまたはqのいずれか一方がnと互いに素でないとき n^{(p-1)(q-1)}≡1 (mod pq)は言えないものの n^{(p-1)(q-1)+1}≡n (mod pq)は言えてしまっているように思えます (私がやったケースはp=3,q=11の場合です)。 これは正しいのでしょうか? 正しいとしたら何故ですか?

  • 電卓でmodの計算

    電卓でmodの計算ってできるんですか? 素数をリュカの判定法により判定する問題がテストに出るんですが、mod計算に時間がかかってしまって。。 わかるかたいらっしゃいましたら、教えてください。