Take the 2-minute tour ×
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.

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|improve this question
1  
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
1  
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
3  
Are you sure this is the correct statement? $n^2+5\gt 4$ for all $n$ so the result is immediate. –  user69810 May 5 '13 at 19:09
    
@amWhy, Yes you are correct, I fixed it –  CodeLover1985 May 5 '13 at 19:30

3 Answers 3

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|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|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|improve this answer

Your Answer

 
discard

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.