# Is my proof correct: if $n$ is odd then $n^2$ is odd?

Prove that for every integer $n,$ if $n$ is odd then $n^2$ is odd.

I wonder whether my answer to the question above is correct. Hope that someone can help me with this.

Using contrapositive, suppose $n^2$ is not odd, hence even. Then $n^2 = 2a$ for some integer $a$, and $$n = 2(\frac{a}{n})$$ where $\frac{a}{n}$ is an integer. Hence $n$ is even.

-
How do you know a/n is an integer? –  anon Mar 12 '12 at 4:28
You have to consider the two cases of n being even or odd, and show that only the even case is possible. –  marty cohen Mar 12 '12 at 4:31
Is this homework? If not, then it might be simpler not to use a contrapositive approach. Let $n = 2k+1$ and work from there. –  user22805 Mar 12 '12 at 4:31
Ops! I made a mistake in the title edit: I wrote "If my.." instead of "Is my..". –  user2468 Mar 12 '12 at 5:18
A number is even if it has 2 as a factor and odd otherwise, elevating a number to an integer power doesn't add factors to a number... –  badp Mar 12 '12 at 8:32

You will want to use contrapositive for proving the converse of this statement, and in most introductory proof classes the professor should make a point of this. That is to say, for the question you posed the cleanest proof is given as follows,

Claim: If $n$ is odd, then $n^2$ is odd, for all $n \in \mathbb{Z}$.

Proof: Assume that $n$ is odd, then $n=2k+1$, for some $k \in \mathbb{Z}$. Hence, $$n^2 = (2k+1)^2= 4k^2 + 4k + 1 = 2(2k^2 + 2k) +1$$ where $(2k^2 + 2k) \in \mathbb{Z}$. Therefore, $n^2$ is odd as desired.

Whereas, for the converse you will quickly run into trouble if you do not try a proof by contrapositive (Exercise: Try it with a direct proof and see where you get stuck!)

Claim: If $n^2$ is odd, then $n$ is odd, for all $n \in \mathbb{Z}$.

Proof: By contrapositive, the claim is logically equivalent to, "If $n$ is even then $n^2$ is even, for all $n \in \mathbb{Z}$". Assume that $n$ is even, then $n=2k$, for some $k \in \mathbb{Z}$. Hence, $$n^2 = (2k)^2 = 4k^2 = 2(2k^2)$$ where $2k^2 \in \mathbb{Z}$. Therefore, $n^2$ is even as desired.

-
I saw a really nice proof of this on SE tonight. It proves the equivalence ''$n^2$ even iff $n$ even'' in one line. $n(n+1) = n^2 + n$ is even, so $n^2$ and $n$ are either both even or both odd. I've never seen that one before. I thought the contrap was the easiest way to go too until I saw this. –  Patrick Mar 13 '12 at 3:18
OH god that's really clean! Still seems like the way I presented develops a bit more intuition for attempting your first non-trivial proofs in "number theory" though. –  Samuel Reid Mar 13 '12 at 6:46
Sure. In my foundations classes I have them first prove that $n$ even implies $n^2$ even which is an easy direct proof. The opposite direction provides a nice contrast since a direct proof (or so I thought) doesn't readily suggest itself and the contrapositive proof is nice and clean. –  Patrick Mar 14 '12 at 4:39

An integer can be said to be odd if $2$ does not occur in its prime factorization,

since $n$ is odd, $2$ does not not occur in the $prime$ $factorization$ of $n$,

if we write the prime factorization of $n^2$ , $2$ will not occur in this as well, since $n^2$ will have same prime factors as that of $n$ , but with increased powers.

hence $n^2$ will be odd for every odd $n$ .

-
Note that this approach depends crucially on uniqueness of prime factorization. Some of the other answers do not depend on this; indeed they work in any ring. –  Bill Dubuque Mar 12 '12 at 6:08
But all integers have unique prime factorization, –  Tomarinator Mar 12 '12 at 6:14
Almost all integers do. Invoking that powerful theorem for this simple problem is akin to opening a chestnut with a sledgehammer. –  Bill Dubuque Mar 12 '12 at 6:23
0 is even, but can be written as a product of itself and an arbitrary finite collection of primes which need not include 2. –  Mark Bennet Mar 12 '12 at 7:09
@BillDubuque: Shouldn't we encourage new members? Uniqueness of the prime factorization is a powerful theorem, but it's quite elementary, and isn't hard to prove. And I don't think that the OP intended to work in any other ring that $\Bbb{Z}$. –  Beni Bogosel Mar 12 '12 at 12:05

You need to show that $a/n$ is an integer. Try thinking about the prime factorizations of $a$ and $n$.

-

Two bits:

Firstly, to clean your proof up, you might instead go like this. If $n^2 = 2a$, then in particular $2 \mid n^2$. $2$ is a prime, and thus we have at least 1 of $2 \mid n$ or $2 \mid n$. Clearly, one happens $\implies$ both happen, and thus $2 \mid n$. So $n$ is even.

Secondly, what if we didn't use contrapositive?

$m$ is odd means $m = 2k + 1$ for some $k$. Then $m^2 = 4k^2 + 4k + 1$.

-

Hint $\rm\ \ n\ odd\:\Rightarrow\:2\ |\ n\!-\!1\ |\ n^2\! -\! 1\:\Rightarrow\:n^2\ is\ \ldots\:$ since $\rm\:n^2\!-\!1\:$ is even. $\ \$ QED

More conceptually, multiplying by an odd integer preserves parity since $\rm\:(1+2\:k)\:n = n + 2\:k\:n\:$ leaves the same remainder as $\rm\:n\:$ when divided by $2$. Hence the product of odd integers is odd.

As for your proof, that odd $\rm\:n\ |\ 2a\:\Rightarrow\: n\ |\ a\$ requires justification. You could use Euclid's Lemma, prime factorization, or Bezout, e.g. $\rm\:11\ |\ 2a\:\Rightarrow\:11\ |\ 6(2a)\!-\!11a\: =\: a,\:$ which uses the Bezout identity $\rm\: 1 = gcd(2,11) = 6\cdot 2 - 1\cdot 11.\:$ It is easy to generalize that from $11$ to any odd integer.

However, that approach is much more work than need be. Notice that

$$\rm n\ |\ 2\:a\iff \exists\ k\!:\ n\:k\ =\ 2\:a\iff \dfrac{a}n\: =\: \dfrac{k}2,\ \ \ so\ \ \ n\ |\ a\iff 2\ |\ k$$

Generally proving $\rm\:2\ |\ k\:$ is easier than $\rm\:n\ |\ a\:$ since there are only $2$ residue cases to test modulo $2$, i.e. the smaller the divisor the easier the computation of the remainder. Indeed, here it's trivial by the above "more conceptual" proof, viz. since $\rm\:n\:$ is odd, $\rm\:nk\:$ and $\rm\:k\:$ have the same parity, therefore $\rm\:nk = 2\:a\:$ is even implies $\rm\:k\:$ is even. Thus $\rm\:2\ |\ k,\:$ so $\rm\:n\ |\ a.$

-