modに関する証明問題

質問

pをp≡3mod4を満たす素数として、a≡b^2mod pが解を持つとしたとき
a^(p+1)/4 が a の mod p での平方根になる

ことを示したいのですが、どうしてそうなるのか、さっぱりです。

どなたか教えていただけないでしょうか。

回答No.2

yoikagari · ベストアンサー

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

お礼

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

回答No.1

Tacosan

a ≡ b^2 (mod p) を使い, a^(p+1)/4 を 2乗して a になることが言えればいいのでは?

お礼

どうもありがとうございます。