Why is $n^2+4$ never divisible by $3$?

Question

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 1

Hint: What does $-4$ equal to in $\mathbb{Z_3}$?

Answer 2

Consider cases. For example, what happens if $n=3k$, $n=3k+1$, and $n=3k+2$?

Answer 3

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$.

Answer 4

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$!

Answer 5

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}$$

Answer 6

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 !

Answer 7

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.

Answer 8

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.