If $p^2\,$is divisible by 3, why is p also divisible by 3?

Question

I came across this in proving that the $\sqrt{3}$ is irrational

Answer 1

Try proof by contrapositive:

Assume that for some $p$, $3 \nmid p$, then the only two cases are: $p \equiv 1\pmod{3}$ and $p \equiv 2\pmod{3}$. Calcualte $p^2 \mod 3$ and get the conclusion.

Answer 2

Take the contrapositive statement: Prove that if $p$ is not divisible by $3$, then $p^2$ is not divisible by $3$.

Answer 3

Even if you don't know (don't remember) any number theory, you can always write $p=3m+k$ where $m$ is an integer and $k\in\{0,1,2\}$. Then, $$ p^2=(3m+k)^2=9m^2+6mk+k^2. $$ In other for this to be divisible by $3$, $k^2$ has to be divisible by $3$. You can manually check that only $k=0$ works.

Answer 4

I would take an approach by looking at the prime factorization of $p^2$. Since it's a square, the powers of its prime factorization must all be even numbers. Since it's divisible by $3$, it has a $3$ raised to some nonzero even number.

It follows from this that $p$ must also have $3$ in its prime factorization.

Answer 5

This is a particular instance of the Euclid's lemma. It is an easy consequence of prime factorization, but without assuming prime factorization slightly less easy.