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$.
 A: For any integer $n$ we have,
$$n\equiv\{0,1,2\}\pmod3\implies n^2\equiv \{0,1,4\}\equiv \{0,1,1\}\equiv\{0,1\}\pmod3\\ \implies n^2+4\equiv\{4,5\}\equiv\{1,2\}\pmod3\implies n^2+4\not\equiv0\pmod3$$
$$\therefore\quad 3\not\mid n^2+4~\forall~n\in\Bbb{Z}$$
A: Look at the expression mod $3$,
$$n^2 + 4 \equiv n^2 + 1.$$
Could $n^2\equiv 2$? What are the squares mod $3$? $0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4 \equiv 1$. Thus $2$ isn't a square mod $3$!
A: Consider cases. For example, what happens if $n=3k$, $n=3k+1$, and $n=3k+2$?
A: Write $n=3r+q$ with $q\in\{0,1,2\}$. Then
$$
n^2+4=9r^2+6rq+q^2+4=(9r^2+6rq+3)+q^2+1.
$$
The expression in the parentheses is divisible by $3$ whereas inspecting the three possibilities for $q$ reveals that $q^2+1$ is never divisible by $3$.
A: 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.
A: General question: For which odd primes $p$ does $n^2+m^2 \equiv 0 \bmod p$ have solutions, where $m$ is coprime to $p$?
$n^2+m^2 \equiv 0 \implies n^2 \equiv -m^2$
In order for $-m^2$ to be a quadratic residue $\bmod p$, Euler's criterion requires that $(-m^2)^{\frac{p-1}{2}} \equiv 1$. However we already know that Euler's criterion holds for $m^2$, so $(m^2)^{\frac{p-1}{2}} \equiv 1$ and then $(-m^2)^{\frac{p-1}{2}} \equiv 1  \bmod p \iff \frac{p-1}{2} $ is even.
So there are solutions for this when $\frac{p-1}{2} \equiv 0 \bmod 2 \iff p-1 \equiv 0 \bmod 4 \iff p\equiv 1 \bmod 4$
For this particular question, $m=2, \: p=3 \not\equiv 1 \bmod 4$ so there are no solutions.
A: Well, You have two cases
1st case $n$ is odd then $n=2k+1$ for some integer $k$
Then $n^2 + 4 = (2k+1)^2 + 4 = 4k^2 + 4k + 5 = 4k(k+1) +5$
Here we have either $k$ or $k+1$ is even and the other is odd or vice versa and we know that even $\times$ odd = even and so $4k(k+1) + 5 = 4(2m)+5$ for some integer $m$ and so have $8m +5$ Now it's obvious that $3 \nmid 8m+5$ for any integer $m$
2nd case $n$ is even then $n=2k$ for some integer $k$ and so $n^2 +4 = (2k)^2 + 4 = 4k^2 +4 = 4(k^2 +1)$
You should also deduce that 3 doesn't divide $4(k^2 + 1)$ and you are basically done !
A: Hint: What does $-4$ equal to in $\mathbb{Z_3}$?
