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.

  • 2
    $\begingroup$ How do you know a/n is an integer? $\endgroup$ – anon Mar 12 '12 at 4:28
  • $\begingroup$ You have to consider the two cases of n being even or odd, and show that only the even case is possible. $\endgroup$ – marty cohen Mar 12 '12 at 4:31
  • 4
    $\begingroup$ Is this homework? If not, then it might be simpler not to use a contrapositive approach. Let $n = 2k+1$ and work from there. $\endgroup$ – user22805 Mar 12 '12 at 4:31
  • $\begingroup$ Ops! I made a mistake in the title edit: I wrote "If my.." instead of "Is my..". $\endgroup$ – user2468 Mar 12 '12 at 5:18
  • $\begingroup$ 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... $\endgroup$ – 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.

  • 3
    $\begingroup$ 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. $\endgroup$ – Patrick Mar 13 '12 at 3:18
  • $\begingroup$ 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. $\endgroup$ – Samuel Reid Mar 13 '12 at 6:46
  • $\begingroup$ 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. $\endgroup$ – 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$ .

  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 12 '12 at 6:08
  • $\begingroup$ But all integers have unique prime factorization, $\endgroup$ – Tomarinator Mar 12 '12 at 6:14
  • 1
    $\begingroup$ Almost all integers do. Invoking that powerful theorem for this simple problem is akin to opening a chestnut with a sledgehammer. $\endgroup$ – Bill Dubuque Mar 12 '12 at 6:23
  • 2
    $\begingroup$ 0 is even, but can be written as a product of itself and an arbitrary finite collection of primes which need not include 2. $\endgroup$ – Mark Bennet Mar 12 '12 at 7:09
  • 2
    $\begingroup$ @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}$. $\endgroup$ – 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.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.