Determine whether each of the following congruences has a solution in integers.
Anyone know how to do this?
For a prime p, the multiplicative group G = has order p-1.
Suppose we can find g with g^2 = -1. Then g^4 = 1. So g has order 4. But by Lagrange, the order of g divides the order of the mutiplicative group. So 4 | p-1.
Conversely, you should know that G is always cyclic, so we can find g s.t. g has order p-1. Then g^(p-1) = 1, but g^(p-1)/2 is not 1, from which we see g^(p-1)/2 = -1. But then setting x = g^(p-1)/4 we have x^2 = -1.