Use Euler's criterion. is a quadratic residue is even
Let n be a whole number of the form with , and p an odd prime that divides n.
Attempt at a solution
The only relevant case is if p=3 (mod 4).
If I try to calculate mod 3, or mod 4, or mod p, I'm not getting anywhere.
Let me make an attempt to explain in a little more detail.
(Burn me down if I'm wrong.)
From Fermat's little theorem we know that , if p is prime and is not a multiple of p.
The question becomes, what about , assuming p is odd?
That would be either -1 or +1.
And that is basically what Euler's criterion says.
The notation is just a fancy way of writing .
here is the way i look at it:
odd primes come in two flavors, 4n+3 and 4n+1 (since all odd numbers only come in these two flavors).
saying p|(x2+1) is another way of saying that we have a square root of -1 in Zp.
so if we can show that if p = 4n + 3 there is no such root, we are done.
now, since p is prime U(Zp) is a multiplicative group of order p - 1. if p = 4n + 3, then p - 1 = 4n + 2.
this is not divisible by 4, so in this case, U(Zp) can have no element a of order 4, or else |<a>| = 4 would divide |U(Zp)| = 4n + 2, by Lagrange's theorem.
note that in Zp[x], x4 - 1 = (x2 + 1)(x2 - 1). since 1 and -1 account for the roots of x2 - 1, we are left with the roots of x2 + 1. but if a2 = -1, then a is of order 4, and we have no such elements.
Actually, I recently got the hint: what is the order of x in Z/pZx?
When I thought about it (for a long while!), I realized that if p|x2+1, that means that x2=-1 mod p.
In turn that means that |x|=4 in Z/pZx.
Since |x| must divide the order of Z/pZx (Lagrange), it follows that 4|p-1.
Therefore p=1 mod 4.