# Prove that for any integer $n, n^2+4$ is not divisible by $7$.

The question tells you to use the Division Theorem, here is my attempt:

Every integer can be expressed in the form $7q+r$ where $r$ is one of $0,1,2,3,4,5$ or $6$ and $q$ is an integer $\geq0$.

$n=7q+r$

$n^2=(7q+r)^2=49q^2+14rq+r^2$

$n^2=7(7q^2+2rq)+r^2$

$n^2+4=7(7q^2+2rq)+r^2+4$

$7(7q^2+2rq)$ is either divisible by $7$, or it is $0$ (when $q=0$), so it is $r^2+4$ we are concerned with.

Assume that $r^2+4$ is divisible by 7. Then $r^2+4=7k$ for some integer $k$.

This is the original problem we were faced with, except whereas $n$ could be any integer, $r$ is constrained to be one of $0,1,2,3,4,5$ or $6$.

Through trial and error, we see that no valid value of $r$ satisfies $r^2+4=7k$ so we have proved our theorem by contradiction.

I'm pretty sure this is either wrong somewhere or at the very least not the proof that the question intended. Any help would be appreciated.

• This seems fine to me. It's also the most natural and typical approach for this problem. – Michael Burr Sep 9 '17 at 17:38
• "7(7q2+2rq) is either divisible by 7, or it is 0" It is divisible by 7. Period. You know that because of the big honking 7 (7q^2+2rq) is being multiplied by. If it is 0, then it is still divisible by 7 because 0 is divisible by 7. 0 = 7*0. So 0 is divisible by 7. – fleablood Sep 9 '17 at 17:39
• BUt your proof is correct. By trial and error $0,1,2,3,4,5,6$ squared are $0,1,4,9,16,25,26$ and $r^2 + 4$ is $4,,5,13,20,29,30$. – fleablood Sep 9 '17 at 17:41
• Thanks both, quite relieving to hear. And yes you're right fleablood, wasn't sure if that counted but I'll never forget now ;) – quantum285 Sep 9 '17 at 17:45
• Note 4,5,6 are equivalent to -3,-2,-1 so you only have to do half of the equations. – fleablood Sep 9 '17 at 18:15

since we have $$n\equiv 0,1,2,3,4,5,6\mod 7$$ we get $$n^2\equiv 0,1,2,4\mod 7$$ therefore $$n^2+4\equiv 1,4,5,6\mod 7$$

Your proof is correct (fleablood's comment). Let me rephrase a bit:

$A(n):= n^2 +4$; $B(r,q) = 7 q^2 + 2rq;$

$A(n) = 7B(r,q) + (r^2 +4)$.

Fairly simple to show that:

$A(n)$ is divisible by $7 \iff$

$(r^2 +4)$ is divisible $n.$

By inspection

$(r^2 +4) , r = 0,1,2,3,4,5,6,$

is not divisible by $7$.

$\Rightarrow$: $A(n)$ is not divisible by $7$.

Through trial and error, we see that no valid value of r satisfies r2+4=7k

so we have proved our theorem by contradiction.

I'm pretty sure this is either wrong somewhere or at the very least not the proof that the question intended. Any help would be appreciated.

Through trial and error you did $7$ calculations. This is fine and acceptable. The calculations are not divisible by $7$ and you proved the if $n^2 +4$ were ever divisible by $7$ then $r^2 +4$ would have to be an you showed it can't. End of story. Good job.

But it's pretty unsatisfactory to do $7$ calculations off page and say "You can check them for yourselves, for now take my word for it".

Here's a slicker way of saying the exact same thing:

We need to prove that $n^2 + 4 \not \equiv 0 \mod 7$.

If $n^2 + 4 \equiv 0 \mod 7$ then $n^2 \equiv 3 \mod 7$

Now there and $7$ residue classes modulo $7$. They are $[0], [1],[2], [3], [-3]=[4], [-2]=[5],$ and $[6] =[-1]$.

So there are $7$ cases to check.

Case 1: $n \equiv 0\implies n^2 \equiv 0 \not \equiv 3 \mod 7$.

Case 2: $n \equiv \pm 1 \implies n^2 \equiv 1 \not \equiv 3 \mod 7$.

Case 3: $n \equiv \pm 2 \implies n^2 \equiv 4 \equiv -3 \not \equiv 3 \mod 7$.

Case 4: $n \equiv \pm 3 \implies n^3 \equiv 9\equiv 2 \not \equiv 3 \mod 7$.

We are done.

A little more advanced: $0 = 0; 1 = 1; 2=3-1; 3=3;$ and $4... 6 \equiv -3...-1$.

So $n \equiv \pm (3k \pm i)$ where $k,i \in \{1,0\}$

$n^2 \equiv (\pm (3k \pm i))^2 \equiv 9k^2 \pm 6ki + i^2 \equiv 2k^2 \mp ki + i^2$ which has 8 possible values depending on whether $k,i$ equal $0$ or $1$ and whether the $\pm$ is a plus or a minus.

If $k = 0$ then $n^2 \equiv i^2$ which is either $0,1$ depending on the value of $i$.

If $k = 1$ then $n^2 \equiv 2\mp i + i^2$. Which is either $2$ or $4$ depending upon the value of $i$ and the sinage of $\mp$.

But that is probably way too obtuse, isn't it?

Your proof is correct. If you know congruences then we can simplify the first half as

$$\bmod 7\!:\,\ n\equiv r\,\Rightarrow\, n^2+4\equiv r^2+4$$

The work in your brute-force check that $\,r^2+4\,$ has no roots can be halved by using a balanced or signed residue system $\, r\equiv \pm\{0,1,2,3\}\,\Rightarrow\,r^2\equiv \{0,1,4,2\}\Rightarrow\,r^2+4\equiv \{4,5,1,6\}$

Alternatively, more simply $\,r^2\equiv -4\equiv 3\,\Rightarrow\,r\not\equiv0\,\Rightarrow\,r^6\equiv 3^3\equiv -1\,$ contra little Fermat (this is a special case of Euler's criterion for squares).

The question boils down to 3 being a quadratic residue modulo 7 or non-residue

$$n^2+4 \equiv 0 \; (mod\;7)$$ $$n^2\equiv 3 \;(mod\;7)$$

For this we have Legendre symbol

$$\left ( \frac{a}{p} \right )=\begin{cases} & 1\text{ if }a\text{ is a quadratic residue modulo }p\text{ and }p\text{ does not divide }a \\ & -1\text{ if }a\text{ is a quadratic non-residue modulo }p \\ & 0\text{ if }p\text{ divides }a \end{cases}$$

calculated as

$$\left ( \frac{a}{p} \right )=a^{\frac{p-1}{2}}$$

So

$$3^{\frac{7-1}{2}} \equiv 3^{3} \equiv 27 \equiv -1 \;(mod\;7)$$

making $3$ a non-residue modulo $7$.

Thus there is no $n$ that solves the congruence so $n^2+4$ is not divisible by $7$ for any $n$.

A little bit more advanced step that applies the Law of quadratic reciprocity would give that $3$ is a residue of $p$ if and only if

$$p \equiv \; 1, \; 11 \; (mod \; 12)$$

and $7$ does not belong to this group obviously.

• Similarly, notice that if $n^2\equiv 3\pmod{7}$, then $$n^6\equiv (n^2)^3\equiv 3^3\equiv$$ $$\equiv 27\equiv -1\pmod{7},$$ which contradicts Fermat's little theorem. – user236182 Sep 9 '17 at 19:38

Here is a proof that seems a bit roundabout, but it relates simpler methods to Fermat's Little Theorem.

First note that clearly $n^2+4$ will not be a multiple of $7$ if $n$ is one. Now for other values of $n$, raise $n^2+4$ to the power of $7-1=6$:

$(n^2+4)^6=n^{12}+(6)(4)n^{10}+(15)(4^2)n^8+...+4^6$

$\equiv n^{12}+3n^{10}+2n^8+6n^6+4n^4+5n^2+1 \bmod 7$

Note that the coefficients are in geometric progression $\bmod 7$, with common ratio $3\equiv -4$. This is because each binomial coefficient is obtained from an adjacent one by multiplying by $(7-k)/k\equiv -1$.

Now apply Fermat's Little Theorem, thus $n^6\equiv 1, n^8\equiv n^2, n^{10}\equiv n^4, n^{12}\equiv n^6\equiv 1$. After this reduction add terms with like powers and note that most of them cancel. We are left with

$(n^2+4)^6\equiv 1\bmod 7$

This completes the proof that $n^2+4$ must fail to be a multiple of $7$.

We can do a similar analysis with $(n^2-r)\bmod p$, where $p$ is an odd prime, raising the binomial to the power of $p-1$. The binomial coefficients always have the common ratio $-1\bmod p$, which causes the successive coefficients in $(n^2-r)^{(p-1)}$ to have common ratio $r\bmod p$. Then the cancellation noted above always occurs if $r^{(p-1)/2}\equiv -1\bmod p$. Thus if $r^{(p-1)/2}\equiv -1\bmod p$, we end with $(n^2-r)^{(p-1)}\equiv 1 \bmod p$ thus proving that $(n^2-r)$ cannot be a multiple of $p$.