# Divisibility by a prime number p.

Show that the cube of a number is divisible by a prime p then the number is divisible by p.

Here is my attempt so far:

Call the number x. Then from the definition of divisibility, we can say $\frac{x^3}{p}=m$ where $m \in \mathbb{Z}.$

$$\frac{x \cdot x^2}{p}= m \;\;\; \Rightarrow \;\;\; \frac{x}{p}= \frac{m}{x^2}$$

Can I say that $\frac{m}{x^2} \in \mathbb{Z}$ hence showing the thesis to be true? If so why? If not what would be the next step in such a proof.

Thank you very much!!!

You should avoid using symbols such as $\frac{m}{x^2}$ when working in the integers, as a general rule. There are no fractions in the integers.

How do you know, for instance, that $x^2\mid m$? What if $x\mid m$ but $x^2\nmid m$.

Try to generalize as follows:

If $a,b\in \mathbb{Z}$, and $p|ab$, then $p|a$ or $p|b$. This is called Euclid's Lemma and, if you prove it, it should help you prove the assertion.

Edit: Since you've proven it, I'll add some more to give you variety.

Proof 1. By assumption, $p|x^3$. By Euclid's lemma we have $p|x$ or $p|x^2$. If $p|x$, then we are done. Suppose then $p|x^2$. Again, by Euclid's lemma we have $p|x$ or $p|x$. But that is what we are trying to show. $\square$

Proof 2. Assume $p|x^3$. Since every number can be uniquely factored into a product of primes, we can write $x=p_1^{a_1}\cdots p_s^{a_s}$. Consider $x^3=(p_1^{a_1}\cdots p_s^{a_s})^3=p_1^{3a_1}\cdots p_s^{3a_s}$. Since $p|x^3$, it must be in the set $\{p_i| 1\leq i \leq s\}$. But then, $p=p_i$ for some $i$, and is thus in the prime factorization of $x$, i.e. $p|x$.$\square$

The reason why the above proof is not a good place to start learning number theory is because it is essentially claiming $p\nmid x \implies p\nmid x^2 \implies p\nmid x^3$ and does not develop tools such as the $\gcd$ or Euclid's lemma.

• I will review Euclid's Lemma and then return if I am still having trouble. Thank you for the good hint!! Feb 19, 2015 at 3:56
• @mathamphetamines Good luck!
– Eoin
Feb 19, 2015 at 3:57
• If fractions are known, then they can prove very useful for proving results about integers. For example, good luck trying to prove this as quickly and naturally without fractions. Feb 19, 2015 at 4:23
• @BillDubuque Sometimes dividing in the integers can lead you astray. That is the point I wanted to get across. I would argue that proof is a nicer result due to polynomial factoring then it is of fractions, however!
– Eoin
Feb 19, 2015 at 6:21
• @Eoin I posted a solution. If you happen to have any time, would you mind taking a look at it and seeing if it is correct? Feb 19, 2015 at 6:26

Hint: If $p$ is prime, and $p|(xx^2)$ then $p|x$ or $p|x^2$, by Euclid's Lemma.

Euclid's Lemma: If $p \mid ab$ then $p \mid a$ or $p \mid b$ for a prime p.

Let $ab=x^3$, that is let $a=x^2$ and $b=x.$

Next, assume that $p \nmid x^2.$ Since $p \nmid x^2,$ then $p$ and $x^2$ are relatively prime, i.e., $gcd(p,x^2)=1.$

We can write $gcd$ as a linear combination of two integers $v$ and $w.$

$$pv + x^2w = 1$$

Now multiplying through by x we get

$$pxv + x^3w = x$$

Since we know that $p \mid x^3$ and that $p \mid pxv$, then $p \mid (pxv+x^3w)$, hence $p \mid x.$

• This is a good proof. It is in fact stronger then what you needed but it is very good. It is also a proof by contradiction. Notice that you in fact showed $p|x$, $p|x^2$, and $p|x^3$. I'll add a couple of variations to my answer as well so you can get some variety.
– Eoin
Feb 19, 2015 at 6:29
• @ Eoin Thank you for your help and patience! Feb 19, 2015 at 6:30