質問: modに関する証明問題 pをp≡3mod4を満たす素数として、a≡b^2mod pが解を持つとしたとき a^(p+1)/4 が a の mod p での平方根になる ことを示したいのですが、どうしてそうなるのか、さっぱりです。 どなたか教えていただけないでしょうか。
回答: 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を参照してください。