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.
 A: 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$$
A: 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$.
A: 
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?
A: 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$$
by standard Congruence Rules (Sum and Product, or Polynomial Rules).
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 $\,n^2\equiv -4\equiv 3\overset{\rm cube}\Longrightarrow\,n^6\equiv 3^3\equiv -1\,$ contra little Fermat (this is a special case of Euler's criterion for squares). $ $  [note $\,n^2\equiv 3\Rightarrow n\not\equiv 0\,$ so Fermat applies].
A: 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.
A: 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$.
