# 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), 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$$?

• Just $p^3=p\cdot p\cdot p$ and $3$ is a prime number. Mar 1, 2019 at 11:49
• I think you should make it clear that $p$ is a prime number even though this is a convention. Mar 1, 2019 at 11:51
• I didn't know the convention and don't want to restrict p to being a prime. Mar 1, 2019 at 11:52
• Yes, you have to prove it, but just for $r=1$ and $r=2$.
– user65203
Mar 1, 2019 at 11:55
• It's a direct result of the Euclid's lemma. Mar 1, 2019 at 12:02

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

• It's a bit mileading to write "the proof is done with Bezout" since there are also ways to prove it that don't use Bezout. I would have written "One common way to prove it is ..." Readers interested in alternative proofs may find of interest a paper by Pierre Samuuel on possible pedagogical foundations of an elementary number theory course. Mar 1, 2019 at 18:54
• @BillDubuque Right. Mar 1, 2019 at 18:57

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.

$$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$$

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