# If $n^2+10$ is odd then $n$ is odd.

I have been having a little trouble with proofs, and would like to ask for a hint for this statement. I've already started it, however I'm unsure what I should be doing next.

Prove that if $n^2 + 10$ is odd then $n$ is odd.

My answer so far: Suppose that $n$ is an odd integer, and we want to prove $n^2 + 10$ is odd. There exists a $k$ that $n=2k+1$. By substituting for $n$, we get...

$(2k+1)^2 +10$ = $n^2 = 10$

$4k^2 + 4k + 11$ = $n^2 +10$

I am unsure what to do next.

EDIT: Thank you all for your hints and answers! They were all brilliant and my understanding for all kinds of proofs is a heck lot better! So much appreciated!

• $[n^2 + 10]_2 = [n^2]_2 + _2 = [n^2]_2 + 0 = [n^2]_2$. – kba Oct 27 '13 at 19:02
• Hi @kba, what's the name of the notation you are using here? I mean that one with the square brackets. Do you have a link for more information? – Mzn Oct 27 '13 at 23:14
• @Mzn, I don't know what the notation is called, sorry, but it's used in Concrete Abstract Algebra. $[x]_y$ is the remainder of $\frac xy$, so $a \equiv b \pmod c \Leftrightarrow [a]_c = [b]_c$. – kba Oct 27 '13 at 23:52
• – The Chaz 2.0 Oct 28 '13 at 0:12
• @kba, I see, thanks a lot! This book should be on my 'study' list! – Mzn Oct 28 '13 at 16:15

Unfortunately, you're working backward. You've (very nearly) proved that if $n$ is odd, then $n^2+10$ is odd.

Now, if you wanted a proof by contrapositive (the simplest way, really), then suppose that $n$ is even, and prove that $n^2+10$ is also even. For a direct proof, assume that $n^2+10$ is odd, and prove that $n^2$ is then odd, and so $n$ is odd (why?). For a proof by contradiction, assume that $n^2+10$ is odd, but $n$ is even, and derive an absurdity.

• Because even and odd are mutually exclusive and collectively exhaustive, is it still flawed to go backwards? – Nick T Oct 28 '13 at 5:53
• When it comes to actually proving the claim, yes it is. It turns out that $n^2+10$ is even (respectively, odd) if and only if $n$ is even (respectively, odd), but there are many implications whose converse does not hold, so the direction is still important, even in cases like the above. For example, if $n$ is a perfect square, then $n^2$ is, but the converse is not generally true, even though "perfect square" and "not a perfect square" are mutually exclusive and collectively exhaustive over integers $n$. – Cameron Buie Oct 28 '13 at 6:12

For a direct proof, you need to assume that $n^2 + 10$ is odd, and show this means $n$ is odd. In your proof, you assume $n$ is odd, which is what is to be proven.

For a proof by contraposition, we assume $n$ is not odd, i.e., that $n$ is even, and show this means $n^2 + 10$ is even. So assuming $n$ is even, there is an integer $k$ such that $n = 2k$. Then substitute $2k$ into n: $$n^2 + 10 = (2k)^2 + 10 = 4k^2 + 10 = 2(2k + 5)$$ which is clearly divisible by $2$ and is therefore even.

Remember, what the contrapositive of a statement is: To prove $p \rightarrow q$, we can prove the equivalent statement $\lnot q \rightarrow \lnot p$.

• Always teaching -->> =1 – Amzoti Oct 28 '13 at 1:38

Your assumptions are backwards. Given $n^2+10$ is odd, you want to prove that $n$ is odd. Perhaps the easiest way to do this is by proving the contrapositive, which can be stated as

If $n$ is even, then $n^2 + 10$ is even.

What you want to do is prove the contrapositive in proofs of this sort. The tautology is $$(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P).$$

By proving: "If $n$ is even, then $n^2+10$ is even" you will have proven your original theorem.

If $n^2+10$ is odd, then $(n^2+10)-11$ is even. Thus, $n^2-1$ is even.

Then $2|(n^2-1)=(n-1)(n+1)$. As $2$ is prime, we get $2|n-1$ OR $2|n+1$. Thus $n-1$ is even or $n+1$ is even, which proves that $n$ is odd.

First note that $n^2 +10$ is odd if and only if $n^2$ is odd. Then you could note that if $n$ is even, then $n^2$ is even. From this it follows that if $n^2$ is not even, then $n$ is not even.

Below is how I would do it:

If $n^2 + 10$ is odd, then $n^2$ is odd.

This makes sense because an odd integer $+1$ is even, an even integer $+1$ is odd, etc. This is to say that an odd integer plus an even integer will give you an odd integer. So it's reasonable to say that if $n^2 + 10$ is odd, then $n^2$ is odd.

Now we want to prove that if $n^2$ is odd, then $n$ must be odd. We note that there are only two possibilities: either $n$ is even or $n$ is odd. Suppose $n$ is even. Then $n$ is a multiple of two, i.e. $2c = n$ for some $c \in \mathbb{Z}$. So $(2c)^2 = 4c^2$, which is also a multiple of two. So if $n$ is even, then $n^2$ must be even. But $n^2$ isn't even, so $n$ can't be even either. (This step was called proving the contrapositive - explanation below). So $n$ must be odd.

Proving the Contrapositive

This is a useful technique. If we have some statement that says $P$ implies $Q$, i.e. if P, then Q, then the statement if not Q, then not P is logically equivalent to the first one (can you figure out why?). Sometimes it can be easier to prove if not Q, then not P than if P, then Q.

Suppose n=2k is even. Then n^2+10 = 4k^2+10=2(2k^2+5) is also even. Consequently, since all integers > 0 are either even or odd (but not both), when n^2+10 is odd, so is n.

or even simpler,

if $n^2+10$ is odd, then there exists $k \epsilon \mathbb{N}$ such that

$n^2+10 = 2k+1 \Rightarrow n^2 = 2(k-5)+1$

so, $n^2$ must be odd, which implies $n$ is odd.