7
$\begingroup$

I am rereading a book on methods of proof and thought I would try proving that if $n^2$ is odd, then $n$ is odd. The proofs for this that I have seen online mostly involve a proof by contrapositive. I was wondering if this could be done by direct proof instead. I found a direct proof in Mark Bennet's answer to this question. It goes:

Suppose $n^2$ is odd, then $n^2=2m−1$ and $(n+1)^2=2(m+n)$

Now $2$ is prime and $2∣(n+1)^2$ so $2∣n+1$ therefore $n+1=2r$ (for some integer r) whence $n=2r−1$ and $n$ is odd.

I came up with a separate proof and I was wondering if it is logically sound:

Suppose $n^2$ is odd, then $n^2=2m+1$ for some $m \in \mathbb{Z}$.

$n^2=2m+1 \implies n^2-1 = 2m \implies (n+1)(n-1) = 2m$

This shows $(n+1)(n-1)$ is even; for this to be true, at least one of $n+1$ and $n-1$ must be even, which means that $n$ is odd.

Is this proof written well? Does it have gaps? If there are problems with it, I would like to ensure that I do not make those same mistakes in the future.

$\endgroup$
12
  • 1
    $\begingroup$ The proofs are well written. Well done! $\endgroup$
    – Rushabh Mehta
    Jun 13, 2021 at 21:28
  • $\begingroup$ Yes, the proof is fine. $\endgroup$
    – Jair Taylor
    Jun 13, 2021 at 21:33
  • 2
    $\begingroup$ Persuade yourself that "$ab$ even implies $a$ or $b$ even" is not a result obtained by indirect proof $\endgroup$
    – Hagen von Eitzen
    Jun 13, 2021 at 21:36
  • 3
    $\begingroup$ An even bigger problem is that it is not possible to rigorously define "direct proof" informally, so it is not even clear what sort of proofs you allow. So the question is ill-defined. To make such terms precise requires significant background in logic. $\endgroup$
    – Bill Dubuque
    Jun 13, 2021 at 21:48
  • 1
    $\begingroup$ Your proof is fine. (And IMO a lot easier and more straightforward than Mark Bennet's... which is also fine but... not clear or "pretty"). But I'm not sure that either are a "direct" proofor if its "directness" addresses the issues you have with worrying about a contrapositive proof. You assume that if $K$ is odd it may be written as $2m+1$ which is a result of "contrapositive reasoning". ANd that if $ab$ is even then at least one of $a$ or $b$ is even which is also "contrapositive reasoning". On the other hand.... I don't see the urgency of "direct proofs" as much as others. $\endgroup$
    – fleablood
    Jun 13, 2021 at 22:10

3 Answers 3

Reset to default
4
$\begingroup$

Your proof is nice. The problem it has is that when you say "for this to be true", you are hiding the fact that you are assuming one of two things:

  • the Fundamental Theorem of Arithmetic (to say that $2$ has to be a factor of either $n-1$ or $n+1$), or

  • that the product of odd numbers is odd.

The problem with the first one is that the proof of "$n$ even if and only if $n^2$ even" usually appears at the very beginning of Number Theory, before the FTA.

The problem with the second one, is that in the end you are using the kind implication you are trying to avoid by not using the contrapositive.

$\endgroup$
4
  • $\begingroup$ You don't need FTA to infer $p|a\lor p|b$ from $p|ab$. That's the definition of "prime". $\endgroup$
    – MJD
    Jun 13, 2021 at 22:56
  • 1
    $\begingroup$ @MJD No, in elementary texts prime means irreducible (atom), and the above is EL = Euclid's Lemma (equivalent to uniqueness of prime factorizations). That $2$ satisfies EL is provable by a parity case analysis but proving EL for all primes(atoms) requires more, e.g. the Euclidean division algorithm. $\endgroup$
    – Bill Dubuque
    Jun 13, 2021 at 23:07
  • $\begingroup$ Thank you for the answer. I can now see that I skipped some steps in my proof. Would there be a way to fix that portion of the proof (e.g. by stating the FTA) or is a proof by contrapositive the way to go? The reason why I was looking for a more direct proof is because it seems a shame that "$n$ even iff $n^2$ even" proof can be done directly quite easily, while the "$n$ odd iff $n^2$ odd" proof cannot. $\endgroup$
    – Kman3
    Jun 14, 2021 at 0:31
  • $\begingroup$ It's hard to say that a kind of proof doesn't exist. The sleek way to prove what you want (but sleekness is in the eye of the beholder) is to show that "$n$ even implies $n^2$ even" and "$n$ odd implies $n^2$ odd". Together with the fact that any integer is either even or odd (which one wants to show early in the theory anyway), that's a proof. $\endgroup$
    – Martin Argerami
    Jun 14, 2021 at 2:15
3
$\begingroup$

Note that, in your proof, you take for granted that: $$x\cdot y \text{ is even } \Longrightarrow x \text{ is even or } y \text{ is even}$$

However, if you take this for granted, then the first proof can actually be shortened. From $(n+1)^2=2(m+n)$, you get immediately that $(n+1)^2$ is even, so $n+1$ is even and, therefore, $n$ is odd.

So the first proof is more complete in some sense, as it takes care to prove this little intermediate step.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer! I have one quick question: does the fact that $(n+1)$ is even come from the fact that $(n+1)(n+1)$ is even and thus by your statement $n+1$ must be even? $\endgroup$
    – Kman3
    Jun 14, 2021 at 0:27
  • $\begingroup$ @Kman3 Yes, precisely. $\endgroup$
    – Evangelos Bampas
    Jun 14, 2021 at 0:36
0
$\begingroup$

Your proof is all correct except for this one thing when you say that "at least one of $(n-1)$ and $(n+1)$ is even". Note that you got $$(n-1)(n+1)=2m$$ Now the left hand side must be even but also observe that it is the product of two numbers in arithmetic progression with common difference $2$ hence if one is even then other automatically becomes even.
Your proof is correct but the word "at least one of them" can lead to a little bit of ambiguity.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .