7
$\begingroup$

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.

  • 0
    Since @Patrick mentioned it in a comment to an answer below, I'll link to my one-line direct proof of the recent "$n^2$ is even iff $n$ is even" question: http://math.stackexchange.com/a/119358/4092012-03-13

5 Answers 5

12

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.

  • 0
    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.2012-03-14
4

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

  • 0
    @Beni *Uniqueness* of prime factorizations is one of the most subtle points in all of elementary mathematics. Simply because it has an elementary proof does not mean that it is elementary or intuitive. For millenia, it has been - and continues to be - the source of many errors. So, when teaching, it is essential to highlight the role that it plays.2012-03-12
3

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

2

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

2

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