1. ## Divisibility

Explain why n^5 - n is divisible by 5 for n=0,1,2,3,....

Can anyone explain to me how to do this?(without mod - I haven't learnt that)

Thanx

2. Are you sure that's the question?

I might be doing something wrong but if you put 0 in you get:

0^5-0=0

and if you put 1 in you get:

1^5-1=0

I don't think 0 is divisible by 5.

3. Hello,
Originally Posted by xwrathbringerx
Explain why n^5 - n is divisible by 5 for n=0,1,2,3,....

Can anyone explain to me how to do this?(without mod - I haven't learnt that)

Thanx
$\displaystyle n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)$

If $\displaystyle n=5k$ : it is divisible by 5.
If $\displaystyle n=5k+1 \implies n-1=5k$ : it is divisible by 5.
If $\displaystyle n=5k+4 \implies n+1=5k+5=5(k+1)$ : it is divisible by 5.

If $\displaystyle n=5k+2 \implies n^2+1=(25k^2+20k+4)+1=5(5k^2+4k+1)$ : it is divisible by 5.
If $\displaystyle n=5k+3 \implies n^2+1=(25k^2+30k+9)+1=25k^2+30k+10=5(5k^2+6k+2)$ : it is divisible by 5.

You (or rather I...) have done all the possible situations.

Originally Posted by Showcase_22
Are you sure that's the question?

I might be doing something wrong but if you put 0 in you get:

0^5-0=0

and if you put 1 in you get:

1^5-1=0

I don't think 0 is divisible by 5.
yes it is.
a is divisible by b if when a is divided by b, the quotient is an integer (0 is an integer) and the remainder is 0.

4. hmmm....

I've never thought of it like that before.

I was trying to use induction on it and I thought it didn't work with 0.

I'll try it again and post what I get.

5. Moo is on the right track. However, note that

$\displaystyle n^5-n=n(n+1)(n-1)(n^2+1)$

$\displaystyle \color{white}.\hspace{10mm}.$ $\displaystyle =n(n+1)(n-1)(n^2-4+5)$

$\displaystyle \color{white}.\hspace{10mm}.$ $\displaystyle =n(n+1)(n-1)(n^2-4)+5n(n+1)(n-1)$

Now $\displaystyle 5n(n+1)(n-1)$ is divisible by 5, while $\displaystyle n(n+1)(n-1)(n^2-4)=(n-2)(n-1)n(n+1)(n+2)$ is the product of 5 consecutive integers and so is also divisible by 5; hence their sum is divisible by 5.

6. Here's what I did. I think it's right but it would be great if someone could check it. It's been a while since i've done any induction.

7. You did not show that $\displaystyle (k-5)(k+1)(k+2)(k^2+2k+2)$ is divisible by 5 for all $\displaystyle k$, only that it’s divisible by 5 for $\displaystyle k=5.$ That’s not good enough.

If you want to use induction, there is no need to factorize. Just use $\displaystyle (n+1)^5-(n+1)=(n^5-n)+5(n^4+2n^3+2n^2+n).$

8. I have to admit that I got a little stuck on that bit.....

9. Yes, you got it.

Note, however, that you do not say, “Assume true for n=k+1.” You are supposed to prove it is true for $\displaystyle n=k+1$, not assume it is true.

10. I thought that you assumed it was true for n=k+1 and you could only say it is true after you've proven it?

In this case, I assumed it was true and worked through it. If it wasn't true I wouldn't have ended up with something that was divisible by 5 at the end.

11. You don’t assume it is true for $\displaystyle n=k+1$. In proof by induction, you assume your formula is true for $\displaystyle n=k$, then prove it is true for $\displaystyle n=k+1$.

Be careful what you can and cannot assume in proving something. In proof by contradiction, you assume that the result you want to prove is false, then show that this leads to a contradiction. However, you never assume what you want to prove is already true before proving it. This fallacy is called “begging the question”.

12. ahhhh, I get it!

However, you never assume what you want to prove is already true before proving it. This fallacy is called “begging the question”.
So I was begging the question when I assumed it was true for n=k+1 ie. I assumed it was true before I had proven it.

Well I won't make tha mistake again. Thankyou!