# Proofs and Number theory

I am needing help proving the following:

For any integer $n$, $n^2$ + 5 is not divisible by $4$

I am aware that an integer $x$ is divisible by integer $y$ if there exists integer $k$ such that $yk = x$. But I am not sure if i need to prove this by contradiction or another exact approach.

-
Look at the possible values of $n^2+5\pmod 4$. That's a good place to start. –  Ian Coley May 5 '13 at 19:09
Do you mean that $n^2 + 5$ is not divisible by 4? or that $4$ does not divide $n^2 + 5$? –  amWhy May 5 '13 at 19:09
Are you sure this is the correct statement? $n^2+5\gt 4$ for all $n$ so the result is immediate. –  John Douma May 5 '13 at 19:09
@amWhy, Yes you are correct, I fixed it –  CodeLover1985 May 5 '13 at 19:30

The statement $4$ is not divisible by $n^2+5$ is trivial, since $n^2+5 \geq 5$.

I assume you want to prove that $n^2+5$ is not divisible by $4$. If so, you can proceed as follows: Note that $$n^2 \equiv \begin{cases} 0 & \text{ if } n \equiv 0,2 \pmod 4\\ 1 & \text{ if } n \equiv 1,3 \pmod4 \end{cases}$$ Hence, $$n^2+5 \equiv \begin{cases} 1 & \text{ if } n \equiv 0,2 \pmod 4\\ 2 & \text{ if } n \equiv 1,3 \pmod4 \end{cases}$$

-

We want to show that $n^2 + 5$ is never equivalent to $0$ modulo $4$: this is the same thing as saying it will not ever be a multiple of $4$ (I assume you meant that you want to show $n^2 + 5$ is not divisible by $4$; the other way around can be checked very quickly by hand). The squares mod $4$ are as follows: $$0^2 \equiv 0\mod 4,$$ $$1^2 \equiv 1\mod 4,$$ $$2^2 \equiv 4\equiv 0\mod 4,$$ $$3^2\equiv 9\equiv 1\mod 4.$$ So, we just need to check that $0 + 5\not\equiv 0\mod 4$ and $1 + 5\not\equiv 0\mod 4$, and we'll be done. But $$5\equiv 1\not\equiv 0\mod 4$$ and $$1 + 5\equiv 2\not\equiv 0\mod 4,$$ so that $n^2 + 5\not\equiv 0\mod 4$ for any $n\in\Bbb Z$, which means that $n^2 + 5$ is never divisible by $4$.

-

I see that other answers apply the congruence method directly, but I think that unveiling this notation and seeing how it works are of some use still.
If $4\mid n$, say $n=4k$, then $$n^2+5=16k^2+25=4(4k^2+6)+1$$ is certainly not divisible by $4$.
If $n=4a+b$, where $b=1, 2, 3$. Then $$n^2+5=16a^2+8ab+b^2+5=4(4a^2+2ab)+b^2+5.$$ So if $n^2+5$ is divisible by $4$, then so is $b^2+1$. But this is impossible for $b=1, 2, 3$.
So the statement follows. In fact, this is nothing but untailing the details of the congruence notation, thus permitting one to see the power of this seemingly innocent congruence notation.
Barring mistakes, and thanks for the attention.

-