Use Euler's criterion. is a quadratic residue is even
Problem statement
Let n be a whole number of the form with , and p an odd prime that divides n.
Proof: .
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.
Help?
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|(x^{2}+1) is another way of saying that we have a square root of -1 in Z_{p}.
so if we can show that if p = 4n + 3 there is no such root, we are done.
now, since p is prime U(Z_{p}) 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(Z_{p}) can have no element a of order 4, or else |<a>| = 4 would divide |U(Z_{p})| = 4n + 2, by Lagrange's theorem.
note that in Z_{p}[x], x^{4} - 1 = (x^{2} + 1)(x^{2} - 1). since 1 and -1 account for the roots of x^{2} - 1, we are left with the roots of x^{2} + 1. but if a^{2} = -1, then a is of order 4, and we have no such elements.
Thanks!
Actually, I recently got the hint: what is the order of x in Z/pZ^{x}?
When I thought about it (for a long while!), I realized that if p|x^{2}+1, that means that x^{2}=-1 mod p.
In turn that means that |x|=4 in Z/pZ^{x}.
Since |x| must divide the order of Z/pZ^{x} (Lagrange), it follows that 4|p-1.
Therefore p=1 mod 4.