# If $p^2\,$is divisible by 3, why is p also divisible by 3? [duplicate]

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

## marked as duplicate by abiessu, MJD, BlackAdder, Adam Hughes, user147263 Sep 5 '14 at 3:24

• $p^2$ has two factors, $p$ and $p$, therefore a $3$ must come from $p$ or $p$. Hey... there's a $3$ in $p$, therefore $3|p$ – Dane Bouchie Sep 5 '14 at 2:37
• $q$ is a prime if and only if $q\mid ab$ implies $q\mid a$ or $q\mid b$. – Frudrururu Sep 5 '14 at 2:43

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

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.

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.

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.

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.