Why is $n^2+4$ never divisible by $3$? Can somebody please explain why $n^2+4$ is never divisible by $3$?  I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible by $4$.

Answer using Quadratic Reciprocity. 
We use Euler's criterion, which states that $n \in \mathcal QR(p)$ iff $n^{\frac {p-1}{2}} \equiv 1 \bmod p$.
We use the Legendre symbol $(\frac np) = \begin{cases} 1 \text{, n} \in \mathcal QR(p)\\
-1 \text{, n} \in \mathcal NR(p)\end{cases}$
for the sake of contradiction, assume $3 \mid n^2+4$
$3 \mid n^2+4 \Rightarrow n^2 +4 \equiv 0 \bmod 3 \\ 
\Rightarrow n^2 \equiv -4 \bmod 3 \\ 
\Rightarrow  -4 \in \mathcal {QR}(3)$ 
Because $-4 \equiv -1 \bmod 3$, $-4 \in \mathcal {QR}(3) \Rightarrow -1 \in \mathcal {QR}(3)$
Now, use Euler's criterion to compute $(\frac {-1}3)$ 
$(-1)^{\frac {3-1}{2}}=(-1)^1 = -1 \Rightarrow -1 \in \mathcal NR(3)$. 
A contradiction! Thus, $3 \nmid  n^2+4$ for any n.
