Proving $3\mid p^3 \implies 3\mid p$ 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$?
 A: 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$.

A: $$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$$
A: 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.
A: 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$.
