2
$\begingroup$

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.

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Palu Oct 14 '17 at 4:29
  • $\begingroup$ 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 $\endgroup$ – LostInSpace Oct 14 '17 at 4:31
  • $\begingroup$ 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. $\endgroup$ – Palu Oct 14 '17 at 4:44
  • $\begingroup$ Thanks I am also interested to read other answers ...and learn from them I put this on favorite.. $\endgroup$ – LostInSpace Oct 14 '17 at 4:46
5
$\begingroup$

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 :)!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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". $\endgroup$ – Palu Oct 14 '17 at 3:39
  • $\begingroup$ 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. $\endgroup$ – Palu Oct 14 '17 at 3:45
  • $\begingroup$ So user296602, is my logic of how to do the contrapositve proof of this correct? $\endgroup$ – Palu Oct 14 '17 at 3:47
2
$\begingroup$

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

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