# Prove that if $5|n^3$ then $5|n$.

I have this very basic number theory type proof that is causing me some headaches and I know it is probably very simple.

I want to prove that if $5|n^3$ then $5|n$.

I have a condition that I am imposing here, one cannot use GCD function.

It is quite obvious to me that $5|n$, due to the fact that $n^3$ is $n*n*n$, and when dividing by $5$, its obvious that it must divide into one of the duplicate '$n$' here. I am not sure if this can be done via a contrapositive proof or proof by contradiction. It seems to me that it can be done via a direct proof.

So if someone can help with a proof of this, would really appreciate it.

• If $5$ is not a divisor of $n$ where do come from that $5$ is a divisor of $n^3$? – Raffaele Oct 14 '17 at 15:37

if $5|n^3$ and 5 doesn't divide n then we must have $5|n^2$

$$\frac {n³}{5}= n\left(\frac {n^2}{5}\right)$$

if $5|n^2$ and 5 doesn't divide n then we must have $5|n$

$$\frac {n^2}{5}= n\left(\frac {n}{5}\right)$$

So if $5|n^3$ then $5|n$

• This seems like a good one! It seems like a simple proof most people would understand with very elementary math skills. This is what I always try to strive for, trying to prove something with minimal amounts of more advanced concepts, just with the most basic elementary school knowledge. – Palu Oct 14 '17 at 4:29
• Yes @Palu its minimalist. We suppose the opposite of what we wanna prove then show a contradiction..And like you I do like elementary proof too – LostInSpace Oct 14 '17 at 4:31
• This looks I guess logical to me. So I will give your answer as the accepted answer Isham. BUT I hope for more people to still give a response to this. It is very interesting to see other ways to prove this. – Palu Oct 14 '17 at 4:44
• Thanks I am also interested to read other answers ...and learn from them I put this on favorite.. – LostInSpace Oct 14 '17 at 4:46

Yes, From Euclid's Lemma if $p$ is a prime number and $p$ divides $a.b$ , $a,b$ positive integers then $p|a$ or $p|b$.

Here $p = 5 | n^3$ or $p | n$ or $p|n^2$.

If $p|n$ we are done!

For the other case of $p|n^2$ then $p|n$ or $p|n$ so we are done again :)!

Based on the level of your question, I suppose you don't know a lot of facts about prime numbers. So this one is most easily handled by contrapositive. Suppose $5 \nmid n$, meaning that $n = 5k + j$ for some integers $k$ and $j$, with $j \in \{1, 2, 3, 4\}$ (why can I assume this??).

Then work through four cases, computing $n^3$. For example,

$$(5k + 1)^3 = 125 k^3 + 75k^2 + 15k + 1 = 5(25k^3 + 15k^2 + 3k) + 1$$

is not divisible by $5$.

• Yes, you are correct user296602, I don't know stuff about primes like Euclids lemma or about n being expressed as a product of primes with powers. So these are the restrictions I am placing. So you figured out correctly that I "don't know a lot of facts about primes". – Palu Oct 14 '17 at 3:39
• I can see that you are adding 1,2,3,4 to 5k, due to the fact that for the next mulitiple of 5, you need to add 5. SO adding 1,2,3,4 will create a number that is not divisible by 5. SO by contrapositive proof that would mean that if i suppose 5 does not divide n then I need to show that it does not divide these 4 cases of n^3. BY THE WAY, I like the fact you know how to do the symbol of "not divide" in MathML. – Palu Oct 14 '17 at 3:45
• So user296602, is my logic of how to do the contrapositve proof of this correct? – Palu Oct 14 '17 at 3:47

$5$ is a prime number and $n^3=n\cdot n\cdot n$.

Thus, $n$ is divided by $5$.

If $n$ is not divided by $5$ then $n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k},$ where $\alpha_i\in\mathbb N\cup\{0\}$, $p_i$ are primes and $p_i\neq5$.

Thus, $n^3=p_1^{3\alpha_1}p_2^{3\alpha_2}...p_k^{3\alpha_k}$ is not divisible by $5$, which is a contradiction.