How do we know 3 is a divisor?

Question

The following is a supposedly true claim, and I came across it in the Coursera course Introduction to Mathematical Thinking (Assignment 7/7) as part of an explanation by the instructor to the proof why $\sqrt{3}$ was irrational. The line that perplexes me goes like this:

If 3 divides the square of some x ∈ ℕ without a remainder, then 3 also divides x without a remainder.

How do we know that this is true for all squared natural numbers?

Answer 1

If $x$ is not a multiple of 3, then either $x=3k+1$ or $x=3k+2$

For $x= 3k+1$, we get $x^2 = 9k^2+6k+1 = 3(3k^2+2k)+1$

For $x= 3k+2$, we get $x^2 = 9k^2+12k+4 = 3(3k^2+2k+1)+1$

As you notice, in either case $x^2$ is not a multiple of $3$

Thus is $x^2$ is a multiple of $3$, then $x$ must be a multiple $3$

Answer 2

It does not hold only for squared natural numbers. It simply results from this more general result:

Euclid's lemma: If a prime $p$ divides a product of natural numbers, it divides at least one of the factors.

As in the present case there's only a repeated factor…