Question

Let gcd(a, p) = 1 with p a prime. Show that if a has at least one square root, then a has exactly 2 roots. [hint: look at generators or use x^2 = y^2 (mod p) and use the fact that ab = 0 (mod p) the one of a or b must be 0(why?) ]

Answer 1

Solution 1 :

Suppose that y is a square root of a (mod p).

Thus, the quadratic congruence x² = a (mod p) has a solution y (mod p). Therefore, x² = y² (mod p) and hence, x²-y² = 0 (mod p). Hence, p | (x² - y²) and thus, p | (x+y)(x-y). Since p is a prime, p | (x+y) or p | (x-y). Hence, x = - y (mod p) or x = y (mod p). Hence, {y,-y} are the 2 solutions of the above quadratic congruence. Thus, if a has at least one square root, then it has exactly 2 square roots.

Solution 2 :

Observe that if p is a prime, then Z/pZ is a field.

Now, consider the polynomial s(x) = x² - a in (Z/pZ)[x]. Firstly, observe that since s has degree 2, hence it has atmost 2 roots in Z/pZ.

Note that the roots of this polynomial in any extension field of Z/pZ are exactly the square roots of a. Since s has atmost 2 roots in Z/pZ, hence a has atmost 2 square roots (mod p).

Now, suppose that b is a square root of a in Z. Then, b is a root of s in Z/pZ.

Thus, in (Z/pZ)[x], x-b | s. Since the leading coefficient of s is 1, there exists a monic linear polynomial x-c in (Z/pZ)[x] such that s(x) = x² - a = (x-b)(x-c). Thus, s(c) = 0 in Z/pZ and consequently, c is also a root of s in Z/pZ. Thus, c is a square root of a (mod p). Thus, a has exactly 2 square roots (mod p).

This proves the claim.