prove (n^5 - n) is divisible by 5 by induction

Fizza

here's what Ive done so far...

P(n) = n^5 - n
n(n-1)(n^3+n+1)
when n = 5
5 * 4* 131 = 620
620 is a factor of 5. therefore true for n=5

assume true n=k
P(k) = k^5 - k

when n = k+1

P(k+1) = (k+1)(k+1-1)((k+1)^3 + k+2)
= (k+1)(k)(k^3 + 3k^2 + 3k + 1 + k + 2)
= (k+1)(k)(k^3 + 3k^2 + 4k + 3)
= (k^2+k)(k^3 + 3k^2 + 4k + 3)
= k^5 + 4k^4 + 7k^3 + 7k^2 + 3k

what shall I do from there?

thanks xxx

mathman

(n+1)^5=n^5+5n^4+10n^3+10n^2+5n+1
Therefore (n+1)^5-(n+1)=n^5-n+K, where K is divisible by 5.

HallsofIvy

Fizza, why do you start with n= 5 as base case? The statement is also true for n= 1, 2, 3, and 4.

Also you did not use the fact that you are assuming k⁵- k is a multiple of 5. Follow mathman's suggestion.

dodo

I'm trying to figure out how the problem was built in the first place.

I'd imagine a similar statement is true for any prime power, since the 'prime rows' of the Pascal triangle are divisible by that prime (except for the ending 1's).

HallsofIvy

So you are asking, "Is it true that n^p- n is divisible by p for p any prime?"

Yes, it is and for exactly the reason you state: if p is prime then [itex]\left(\begin{array}{c}p \\ i\end{array}\right)[/itex] for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition:
[tex]\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}[/tex]
as long as i is neither 0 nor p, 0<p-i< p and so neither i! nor (p- i)! have a factor of p. Since p! does, the binomial coefficient is divisible by p. (We need p to be prime so that other factors in i! and (p- i)! do not "combine" to cancel p.)

Now, to show that n^p- n is divisible by p, do exactly what mathman suggested.

First, when n= 1, 1^p- 1= 0 which is divisible by p. Now assume the statement is true for some k: k^p- k= mp for some integer m. Then, by the binomial theorem,
[tex](k+1)^p= \sum_{i=0}^p \left(\begin{array}{c}p \\ i\end{array}\right) k^i[/itex]
subtracting k+1 from that does two things: first it cancels the i=0 term which is 1. Also we can combine the "k" with the i= p term which is k^p so we have k^p- k= mp. The other terms, all with 0< i< p, contain, as above, factors of p.

googlymunja32

What would be the converse of this ^^^? Could you use "the assuming the opposite" method to prove whether or not this holds?

cheers

LowlyPion

Not to be too picky but your example shows n = 5 yields 620. It should be 2620, but of course satisfies the condition.

Secondly and more importantly I don't think the factors of n^5 - n are simplified enough.

I would note that:
n^5 - n = n(n^4-1) = n*(n^2-1)*(n^2+1) = (n-1)*n*(n+1)*(n^2+1)

Perhaps you can exploit the fact that for any n you necessarily have the number above and below that number that must be a factor of the result?