4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ When you say "there is an example with n^2+1", what exactly do you mean? $\endgroup$ – hardmath Apr 29 '15 at 1:58
  • $\begingroup$ 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 . $\endgroup$ – steven gregory Apr 29 '15 at 2:06
18
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Definetely concise and yet simple! +1 $\endgroup$ – imranfat Apr 29 '15 at 2:11
  • 1
    $\begingroup$ I honestly think this is the nicest/clearest answer. +1 $\endgroup$ – Daniel W. Farlow Apr 29 '15 at 2:17
  • 1
    $\begingroup$ $n^2+4$ is divisible by three iff $n^2+1$ does! Hence your first paragraph is a complicated way! $\endgroup$ – k1.M Apr 29 '15 at 13:24
  • 1
    $\begingroup$ @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. $\endgroup$ – Kim Jong Un Apr 29 '15 at 22:19
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$ – Mike Pierce Apr 29 '15 at 2:20
  • 4
    $\begingroup$ @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. $\endgroup$ – Ebearr Apr 29 '15 at 2:23
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ What is a ftsoc? $\endgroup$ – Théophile Apr 29 '15 at 13:06
  • $\begingroup$ 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. $\endgroup$ – Jamie Lannister Apr 29 '15 at 13:15
  • $\begingroup$ 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. $\endgroup$ – Jamie Lannister Apr 29 '15 at 13:20
  • $\begingroup$ tweaked formula usage and cleaned up a little. Of course there is another QR for any $p: 0$. $\endgroup$ – Joffan Apr 29 '15 at 14:01
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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 !

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.