What is wrong with my proof by contradiction that if $n^2$ is divisible by 3, then $n^2$ is divisible by 9?

Question

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?

Answer 1

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

Answer 2

I think your conclusion 4 is not correct in the first case and the statement 1 should be

there exists k such that $n^2$=3*k (where k belongs to integer)

Now coming into the actual proof:-

we have 3 divides $n^2$

implies, 3 divides n (*)

implies 9 divides $n^2$

The statement marked in (*) can be proved trivially by contradiction

Answer 3

You should be saying $k$ is a fixed, nonzero integer (not $k$ is any nonzero integer).

Your proof is incorrect. You didn't get a contradiction.

To do this, I think you need Euclid's lemma: $p\mid ab\implies p\mid a\lor p\mid b$.

Or perhaps the prime factorization.

---

So suppose that $3\mid n^2$. By Euclid's lemma, $3\mid n$. So $n=3k$ for some $k$. Then $n^2=(3k)^2=9k^2$. Hence $9\mid n^2$.

Answer 4

you say

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

Obviously you can't mean $k$ can be any non-zero integer. $k$ can't be ... $5$..., say, because $n^2 = 3*5 = 15$ is simply not possible.

$k$ can be any number so that $3k$ is a perfect square or $k$ can be any $\frac {n^2}3$ so that $\frac {n^2}3$ is an integer but... we really don't at this point of the game have any idea when such numbers are possible and when they are not.

We have to prove that any such $k$ must also be divisible by $3$.

Hint: Consider what happens if $3|n$ or $3 \not \mid n$. If $3|n$ does $9|n^2$? If $3 \not \mid n$ does $3|n^2$?