Suppose that p and q are distinct primes satisfying p q 1 m

Suppose that p and q are distinct primes satisfying p, q = 1 (mod 4) Show that the congruence x^2 = -1 (mod pq) has a solution.

Solution

Let\'s take a general example. Let p = 5 and q = 13 ( distinct primes)

Then, (p,q) mod 4 = 1

If we take x = 8 (x^2 = 64),

x^2 mod p*q = -1      64 mod (13* 5) = -1

SInce, the congruence x^2 mod (pq) = -1 for p = 5, q = 13, x =8

Therefore, it has a solution.