For an odd prime p prove that the congruence 2x210 mod p has

For an odd prime p, prove that the congruence 2(x^2)+1=0 (mod p) has a solution if and only if p = 1 or 3 (mod 8)

Solution

we want 2 to be a square modulo p.

A solution x exists if and only if x² (2)/4 is a square modulo p, if and only if 2 is a square modulo p.

This is because the following congruences modulo p are equivalent:

Now

(2/p) = (1/p) (2/p)

is 1 if and only if p 1,3(mod8).