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.

New to the whole proof thing.

Trying to figure out that, for all integers $n$, if $n^2 + 3$ is even, then $n$ is odd.

Thank you for the help.

share|improve this question

5 Answers 5

up vote 8 down vote accepted

The notation "$m\mid n$" means "$m$ divides $n$," or "$n$ is divisible by $m$." In contrast, $m\not\mid n$ means "$m$ does NOT divide $n$," or put differently, "$n$ is not divisible by $m.$"


Assume $n^2 + 3$ is even.

$(1)$ $n^2 + 3$ is even means, by definition, that $2$ divides $n^2 + 3$: $$2\mid (n^2 + 3) \iff n^2 + 3 = 2k\;\text{ for some}\; k \in \mathbb Z.$$

That is, $n^2 + 3 $ is some integer multiple of of $2$.

Hence $$n^2 = 2k - 3 = 2(k-2) + 1 \implies 2\not\mid 2(k - 2) + 1,\;\implies 2\not\mid n^2$$ since clearly, $\;2 \mid 2(k-2),\;$ but $\;2 \not\mid 1$. In words, $2$ does not divide $n^2$. So $n^2$ is not even, and hence it must be the case that $n^2$ is odd. From $(2)$, it will follow that $n$ is therefore odd.

$(2)$ $n^2$ odd $\iff n$ is odd.

  • $ \implies$ We prove this by proving the contrapositive:
    Assume $n$ is not odd (assume $n$ is even), so $n = 2k$ for some integer $k$. So then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, and so $2$ divides $n^2$, and hence $n^2$ is even, ie. if $n$ is not odd, then $n^2$ is not odd, which gives us, contrapositively: $n^2$ is odd $\implies n$ is odd.

    N.B. (That's really all we need for your proof, but let's go ahead and show that the implication $(2)$ is bi-directional.)

  • $\Longleftarrow$ Assume $n$ is odd. Then $n = 2k + 1 $ for some integer $k$. And so $$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$ Now $2 \not\mid [2(2k^2 + 2k) + 1]$, so $n^2$ cannot be even: That is, if $n$ is odd, then $n^2$ is odd.

share|improve this answer
    
Its probably helpful to explain what $\not\mid , | $ mean if we are working on an introductory proof level. I know i certainly was not familiar with that notation when I was just learning –  MSEoris Mar 25 '13 at 23:38
    
@MSEoris Done...thanks for the opportunity to clarify. –  amWhy Mar 25 '13 at 23:43
2  
Too much verbiage to get to the obvious: if $X + 3$ is even, $X$ must be odd. See Berci's answer. –  Kaz Mar 26 '13 at 4:58
    
Dear god so much text. This proof should take one sentence; see Berci's or Brian's answers... –  BlueRaja - Danny Pflughoeft Mar 26 '13 at 6:50
2  
JustaBreitGuy: Don't mind the two comments above: sure, it might be obvious - but the task didn't ask you to answer "because it's obvious"; it asked you to prove it...and for that, we've done the job! ;-) –  amWhy Mar 26 '13 at 14:25

$n^2+3$ is even $\iff$ $\ n^2$ is odd $\iff$ $\ n$ is odd.

share|improve this answer

HINT: Ask yourself what would happen if $n$ were even. Would $n^2$ be even, or odd? What about $n^2+3$?

share|improve this answer

Hint $\rm\ n^2\!+3 = \color{#C00}{n(n\!-\!1)}\!+\!2+n\!+\!1 = n\!+\!1 + \color{#C00}{even}\!+\!2\, $ is even $\rm\!\!\iff\!\! n\!+\!1\,$ even $\rm\!\!\iff\!\!n\,$ odd

Or, $\rm\,\ \ mod\ 2\!:\,\ \ \color{#C00}{n^2 \equiv\, n}\:\Rightarrow\:n^2\!+3\,\equiv\, n\!+\!1\equiv 0\!\iff\! n\equiv 1,\ \ $ i.e. $\rm\ \ n^2\!+\!3\ \smash[t]{\stackrel{(even)}{\equiv\ 0}\,\iff\, \stackrel{\ \ \ (odd)}{n\equiv 1}}$

share|improve this answer

If $n^2 + 3$ is even then $n^2 + 3 = 2k$ , where $k$ is an integer.
Thus, $n^2 = 2k - 3 = 2k - 4 + 1 = 2(k-2) + 1$, where $k$ is an integer, which means $k-2$ is an integer.
Now, this implies that $n^2$ is odd.
Assume $n$ is even.
Then $n$ can be written in the form $2m$, where $m$ is an integer.
Thus, $n^2 = (2m)^2 = 4m^2 = 2(2m^2)$.
We know $2m^2$ is an integer.
Thus $n^2$ is even.
But this gives us a contradiction because we already have established that $n^2$ is odd.
Therefore $n$ is odd.

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.