# Why is $n^2+4$ never divisible by $3$? [duplicate]

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

• When you say "there is an example with n^2+1", what exactly do you mean? – hardmath Apr 29 '15 at 1:58
• Let me paraphrase what you just said. Three doesn't go into 9 + 1 but you can write 4 as 3 + 1 and factor out a 3, so four goes into 9 + 4 . – steven gregory Apr 29 '15 at 2:06

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

• Definetely concise and yet simple! +1 – imranfat Apr 29 '15 at 2:11
• I honestly think this is the nicest/clearest answer. +1 – Daniel W. Farlow Apr 29 '15 at 2:17
• $n^2+4$ is divisible by three iff $n^2+1$ does! Hence your first paragraph is a complicated way! – k1.M Apr 29 '15 at 13:24
• @k1.M The problem is simple enough anyway. It is then a matter of tailoring the answer to suit OP's needs and background. e.g. I intentionally avoided $\text{mod}$. Thanks. – Kim Jong Un Apr 29 '15 at 22:19

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

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

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

• This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. – Mike Pierce Apr 29 '15 at 2:20
• @mapierce271 I am not requesting clarification or critiquing. Just because I didn't spoon feed the answer doesn't mean it's not an answer. This guides one to a solution. – Ebearr Apr 29 '15 at 2:23

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.

• What is a ftsoc? – Théophile Apr 29 '15 at 13:06
• We assume that $3|n^2+4$. If this is true, then $-4 \in \mathcal QR(p)$ and hence, $-1 \in \mathcal QR(p)$. However, $-1 \in \mathcal NR(p)$ a contradiction. – Jamie Lannister Apr 29 '15 at 13:15
• Clarified that now. I wanted to go through the general strategy since using quadratic residues is a good tool for general instances of these types of proofs. – Jamie Lannister Apr 29 '15 at 13:20
• tweaked formula usage and cleaned up a little. Of course there is another QR for any $p: 0$. – Joffan Apr 29 '15 at 14:01

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.

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 !

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