3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Just $p^3=p\cdot p\cdot p$ and $3$ is a prime number. $\endgroup$ – Michael Rozenberg Mar 1 at 11:49
  • $\begingroup$ I think you should make it clear that $p$ is a prime number even though this is a convention. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Mar 1 at 11:51
  • $\begingroup$ I didn't know the convention and don't want to restrict p to being a prime. $\endgroup$ – Robin Mar 1 at 11:52
  • 1
    $\begingroup$ Yes, you have to prove it, but just for $r=1$ and $r=2$. $\endgroup$ – Yves Daoust Mar 1 at 11:55
  • 1
    $\begingroup$ It's a direct result of the Euclid's lemma. $\endgroup$ – rtybase Mar 1 at 12:02
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 1 at 18:54
  • $\begingroup$ @BillDubuque Right. $\endgroup$ – egreg Mar 1 at 18:57
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.