Proving $3\mid p^3 \implies 3\mid p$

Question

I want to prove $3\mid p^3 \implies 3\mid p$ (Does it?)

The contrapositive would be $3 \nmid p \implies 3 \nmid p^3$ I believe.

$3\nmid p \implies p = 3q + r$ ($0<r<3$), so $p^3 = 27q^3+27q^2r+9qr^2+r^3$

Dividing by $3$ we get $3(9q^3 + 9q^2r + 3qr^2) + r^3$

Is this correct so far? How do I finish the proof please? Do I need to show that $r^3$ can never be a multiple of $3$?

Answer 1

Since $0\lt r\lt3$ so either $r=1$ or $r=2$.

If $r=1$ then $r^3=1$ . So $3(9q^3+9q^2r+3qr^2)+r^3=3(9q^3+9q^2r+3qr^2)+1$ which leaves remainder $1$ when divided by $3$

And similarly, if $r=2$ then $r^3=8$ . So

$3(9q^3+9q^2r+3qr^2)+r^3=3(9q^3+9q^2r+3qr^2)+8=3(9q^3+9q^2r+3qr^2)+3\cdot2+2=3(9q^3+9q^2r+3qr^2+2)+2$

which leaves remainder $2$ when divided by $3$.

It follows that both of the two expressions are not divisible by $3$ and you reach to a contradiction.

Answer 2

$$p^3\bmod3=(p\bmod3)^3\bmod 3,$$ so that

$$p\bmod3=0\to p^3\bmod3=0$$ $$p\bmod3=1\to p^3\bmod3=1$$ $$p\bmod3=2\to p^3\bmod3=2$$

Answer 3

A very important property of prime numbers is

if the prime number $x$ divides a product $ab$, then it either divides $a$ or it divides $b$.

A common way to prove it is with Bézout's identity: suppose $x\nmid a$; then, as $x$ is prime, $\gcd(x,a)=1$ and therefore $1=xy+az$ for some integers $y$ and $z$. Therefore $$ b=1\cdot b=xyb+abz $$ is divisible by $x$.

Now prove by induction that

if $x$ is prime and $x\mid y^n$, then $x\mid y$.

Answer 4

Your proof is headed in the correct direction, and you do need to show that $3\not\mid r^3$ if $0\lt r\lt3$. However, it might be easier to simply assume that $3\mid p^3$ and write $p=3q+r$ with $|r|\le1$ (instead of $0\le r\lt3$). Then, since (as you found) $p^3=(3q+r)^3=3(9q^3+9q^2r+3qr^2)+r^3$, the assumption $3\mid p^3$ implies $3\mid r^3$. But $|r|\le1$ implies $|r^3|\le1$, and the only such integer divisible by $3$ is $r^3=0$. Thus $p=3q$, so $3\mid p$.

Note that using $-1\le r\le1$ instead of $0\le r\le2$ is mainly a convenience; it makes the proof a little slicker. The crucial point is that the number of possible remainders is small enough that you can easily deal with all the different cases. I would not recommend taking this approach if the problem were, for example, to prove that $103\mid p^3\implies 103\mid p$.