# Proof of divisibility, given divisibility of a square

The below proof is incorrect. See the answers for more information.

This question is in the context of exploring how to explain the process of developing a proof.

When reading a proof on the irrationality of $\sqrt{3}$, I came across the following statement, which was not proved in the irrationality proof itself.

• If $a^2$ is divisible by 3, then $a$ is divisible by 3.

I believe the following proves the above statement:

1. Let $k$ be an integer, and $a$ be an integer divisible by $n$, where $a=n(k+1)$.
2. $a = nk+n$
3. $a^2 = (nk + n)(nk + n)$
4. $a^2 = n^2(k+1)(k+1)$
5. Therefore, $a^2$ is divisible by $n$.

Although the above proof "feels" valid to me, it also seems like the proof is not complete, in a formal sense, because:

• Constraints are not placed on the variables.
• Although the leap from step 4 to step 5 seems intuitive, there is no formal explanation as to why the step is valid. (It seems like something is missing to explain how to go from divisible by $n^2$ to divisible by $n$.)
• $a$ is divisible by 3 $\implies$ $a^2$ is divisible by 3, but no justification is given for the opposite implication.

All that said, is the above proof sufficient to justify the initial assertion about divisibility by 3? What would formally justify going from step 4 to step 5?

And more generally: Are there objective standards for sufficiency of proof, either published or generally accepted?

• You are not trying to prove $a^2$ is divisible by $n$, assuming $a$ is; that's obvious. You're trying to prove $a$ is, assuming $a^2$ is. – symplectomorphic Jan 19 '15 at 0:57

## 3 Answers

As @mapierce271 pointed out already, your proof doesn't actually accomplish what you've set out to show. I would also like to add that your "theorem" (if $n$ divides $a^2$, then $n$ divides $a$) is not true for just any integer $n$. For example, $8^2=64$ is divisible by $32$, but $8$ is definitely not divisible by $32$. However, it is true if $n$ is a prime number (which $3$ is). The easiest method of showing this will use "Euclid's Lemma": if $p$ is prime and $p$ divides the product $ab$, then $p$ divides $a$ or $p$ divides $b$. You can read more about Euclid's Lemma here: http://en.wikipedia.org/wiki/Euclid's_lemma

• Thank you -- Euclid's lemma (and The Elements, book 7, proposition 30) was exactly what I was looking for. – Thomas Phillips Jan 19 '15 at 2:21

Your proof appears to be the reverse of what you are trying to prove. The original statement is "$a^2$ divisible by $3$ implies that $a$ is divisible by $3$." Your proof starts with "suppose we have $a$ divisible by $n$..." and this lead to "...$a^2$ is divisible by $n$." Your proof should start with "$a^2$ divisible by $n$."

Also, I am curious why you decide to have $(k+1)$ in $a = n(k+1)$. Why not just $k$?

• I had a $(k+1)$ leftover from scribbles on fixing numbers to be odd. I had just gone through the proof that $\sqrt{2}$ is irrational and was searching for a generalization. – Thomas Phillips Jan 19 '15 at 2:26

Congruences allow for a very simple proof of the assertion: ‘ If $a^2$ is divisible by $3$, the $a$ is divisible by $3$.

It suffices to draw up the list of squares modulo $3$:

• if $a\equiv 0\mod 3$, then $a^2\equiv 0^2=0$;
• if $a\equiv \pm 1$, then $a^2\equiv 1 \mod 3$. Hence the only case when $a^2$ is divisible by $3$ is when $a$ itself is.