<s>[INST] 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.
 [/INST] 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$.
</s>