0

I'm trying to write a simple, informal proof to this problem. I know it would likely be simpler to tackle by showing a proof by contraposition, but I'm being asked specifically to write a proof by either contradiction or cases.

In proof by contraposition I think it might look something like this:

Let n be an integer.
If n^2 is not divisible by 9, there is no integer k such that n^2 = 9k.
9k = 3(3k).
Let 3k = m, where m is an integer. Then there is no integer m such that n^2 = 3m.
Therefore n^2 is not divisible by 3.
Therefore if n^2 is not divisible by 9, it is not divisible by 3.
Therefore if n^2 is divisible by 3, it is divisible by 9.

But I'm not sure how you would move from that to proof by contradiction. For proof by contradiction I think you would start out by assuming that n^2 is not divisible by 9 and demonstrating that this creates a contradiction with n^2 being divisible by 3, but I am not sure.

Any help is appreciated, thanks!

Olivier Roche
  • 5,319
  • 9
  • 16
Mariah Lynn
  • 11
  • You could assume $n^2$ is divisible by 3 as a given, and then assume $n^2$ is not divisible by 9 to find the contradiction. – XYZT Feb 04 '22 at 02:14
  • I see that, but it isn't clear to me how I'd write that out in order to show a contradiction. – Mariah Lynn Feb 04 '22 at 02:24
  • 1
    @MariahLynn Contraposition would not be a natural choice to prove this, since the direct proof is so straightforward (Euclid's lemma). – dxiv Feb 04 '22 at 02:27
  • Your proof is wrong. You show there is no $m$ of the form $3k$ such that $n^2 = 3m$, but that doesn't say there is no such integer $m$ at all. – Robert Israel Feb 04 '22 at 02:36
  • @dxiv True! I didn't think of direct proof haha (silly), but either way I unfortunately can't use it here. – Mariah Lynn Feb 04 '22 at 02:37

3 Answers3

1

Let the prime factorization of n be $$ n=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{m}^{\alpha_{m}}, $$ then $$ \begin{array}{rl} \quad n^{2} & =p_{1}^{2 \alpha_{1}} p_{2}^{2 \alpha_{2}} \ldots p_{m}^{2 \alpha_{m}} \\ 3 \mid n^2& \Rightarrow 3 \mid p_{1}^{2 \alpha_{1}} \cdot p_{2}^{2\alpha_{2}} \ldots p_{m}^{2\alpha_{m}} \\ & \Rightarrow 3 \mid p_{i} \quad \exists i \in \{1,2,3, \cdots, m\} \\ & \Rightarrow 3^{2} \mid p_{i}^{2} \\ & \Rightarrow 9 \mid p_{i}^{2 \alpha_{i}} \\ & \Rightarrow 9 \mid n^{2} \end{array} $$

Lai
  • 20,421
0

If $n^2$ is not divisible by 9, then there does not exist a $k$ such that $n^2 = 9 k^2 = (3k)^2$, and so there does not exist an $n = 3k$ (due to 3 being prime and the fundamental theorem of arithmetic). Therefore, $n$ cannot be divisible by 3.

This implies that $n^2$ is not divisible by 3. Contradiction.

XYZT
  • 1,043
  • 6
  • 22
  • 1
    You haven't shown that $n^2$ divisible by $3$ implies $n$ divisible by $3$. This could be done either by cases ($n \equiv 1$ or $2 \mod 3$) or using unique factorization (the fundamental theorem of arithmetic). – Robert Israel Feb 04 '22 at 02:32
0

if $\frac{n^2}{9} = (\frac{n}{3})^2$ not an integer, then $\frac{n}{3}$ not an integer. But $3 | n^2 \implies 3 | n$.

sku
  • 2,643
  • "$3 \mid n^2 \implies 3 \mid n$" $;-;$ This is indeed true, but you have to prove it, otherwise it's just assuming something equivalent to what you set out to prove. – dxiv Feb 04 '22 at 04:02
  • I was assuming we can use if $p | ab$, either $p|a$ or $p|b$ or $p$ divides both. – sku Feb 04 '22 at 06:43
  • You need to at least state that explicitly. And, once you do, the entire proof can be reduced to $,3 \mid n^2 \implies 3 \mid n \implies 3^2 \mid n^2,$. – dxiv Feb 04 '22 at 07:04