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 $\displaystyle p>3$. There are two cases: $\displaystyle p\equiv 1(\bmod 4)$ or $\displaystyle p\equiv 3(\bmod 4)$. In the first case we get $\displaystyle (3/p) = (p/3)$. Now if $\displaystyle p\equiv 1(\bmod 3)$ then $\displaystyle (p/3) = (1/3)=1$ and if $\displaystyle p\equiv 2(\bmod 3)$ then $\displaystyle (p/3) = (2/3) = -1$, therefore $\displaystyle p\equiv 1(\bmod 3)$ in the first case. Together $\displaystyle p\equiv 1(\bmod 4)$ and $\displaystyle p\equiv 1(\bmod 3)$ give us $\displaystyle p\equiv 1(\bmod 12)$.
In the second case we get $\displaystyle (3/p) = -(p/3)$ and to get $\displaystyle (3/p) = 1$ it is necessary and sufficient to get $\displaystyle (p/3) = -1$. Now this happens when $\displaystyle p\equiv 2(\bmod 3)$. We have $\displaystyle p\equiv 3(\bmod 4)$ and $\displaystyle p\equiv 2(\bmod 3)$ which is equivalent to $\displaystyle p\equiv -1(\bmod 4)$ and $\displaystyle p\equiv -1(\bmod 3)$. Together this combines into $\displaystyle p\equiv -1(\bmod 12)$.