If $p^2\,$is divisible by 3, why is p also divisible by 3? I came across this in proving that the $\sqrt{3}$ is irrational
 A: Take the contrapositive statement: Prove that if $p$ is not divisible by $3$, then $p^2$ is not divisible by $3$.
A: 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.
A: 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.
A: 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.
A: 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.
