# Proof: How to prove $n$ is odd if $n^2 + 3$ is even

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.

-

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.

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

-

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

-

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

-

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.

-