Let p be an odd prime number. Prove that
(3 over p) =1 if and only if p = +-1 mod 12
where (3 over p) denotes the legendre symbol.
Let . There are two cases: or . In the first case we get . Now if then and if then , therefore in the first case. Together and give us .
In the second case we get and to get it is necessary and sufficient to get . Now this happens when . We have and which is equivalent to and . Together this combines into .