Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 – CodingWonders90 May 5 '13 at 19:30
up vote 4 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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