Wrong with the proof by contradiction that if $n^2$ is divisible by 3, then $n^2$ is divisible by 9

elementary-number-theoryproof-verification

I'm working through the book Language, Proof and Logic (2nd ed., Barker-Plummer, Barwise & Etchemendy). This is problem 5.25, presented right after the introduction to proof by contradiction.

Prompt: Assume that $n^2$ is divisible by 3. Prove that $n^2$ is divisible by 9.

Here's my take on it:

  1. Assume that $n^2 = 3k \text{ (k being any non-zero integer)}$
  2. Let $n^2 \neq 9m \text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
  3. From 2, $n^2 \neq 3(3m)$.
  4. From 1, 3, we have $k \neq 3m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 9m \text{ (for a non-zero integer m)}$.

The problem is that, I don't think this is right because I can replace 9 with 81 and do:

  1. Assume that $n^2 = 3k \text{ (k being any non-zero integer)}$
  2. Let $n^2 \neq 81m \text{ (m being any non-zero integer)}$ (i.e, not divisible by 9)
  3. From 2, $n^2 \neq 3(27m)$.
  4. From 1, 3, we have $k \neq 27m$. But we have previously said that $k$ can be any non-zero integer. Hence, a contradiction, so $n^2 = 81m \text{ (for a non-zero integer m)}$. Which I can refute giving a counter example n = 3.

I don't think this chapter restrict me to using only proofs by contradiction, but it only allows me to use basic arithmetics and definitions of even / odd (and also prove by cases). I think this answer should satisfy the requirement by the book.

Yet, I'm curious about what is wrong about my way of proving by contradiction?

Best Answer

"Assume that $n^2 = 3k$ ($k$ being any non-zero integer)."

There is the problem. $k$ is some integer. Since $n^2$ is a fixed number, $k$ cannot be anything you want.

The place where you attempt to reach a contraction, "But we have previously said that $k$ can be any non-zero integer" therefore doesn't work.

Related Question