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:
- Let $k$ be an integer, and $a$ be an integer divisible by $n$, where $ a=n(k+1) $.
- $ a = nk+n $
- $ a^2 = (nk + n)(nk + n) $
- $ a^2 = n^2(k+1)(k+1) $
- 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?
Best Answer
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