题目

a是一个整数的完全平方 p是质数 求x^2≡a(mod p)有多少解?

提问时间：2021-01-28

答案

设x^2≡a(mod p)有某两个不同的解r1, r2则
r1^2≡a(mod p)
r2^2≡a(mod p)
相减
(r1-r2)(r1+r2)≡0(mod p)
p是质数,所以r1-r2≡0(mod p)
或者r1+r2≡0(mod p)
即r1≡正负r2(mod p)
所以x^2≡a(mod p)最多有两个解.
设a=r^2
当r≡0(mod p)时,则r＝0是x^2≡a(mod p)仅有的1个解
当r不≡0(mod p)时则正负r是x^2≡a(mod p)仅有的2个不同解