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

by Fizza
Tags: divisible, induction, prove
 P: 1 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
 Sci Advisor P: 5,772 (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.
 PF Patron Sci Advisor Thanks Emeritus P: 38,412 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 k5- k is a multiple of 5. Follow mathman's suggestion.
P: 687

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

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).
 PF Patron Sci Advisor Thanks Emeritus P: 38,412 So you are asking, "Is it true that np- n is divisible by p for p any prime?" Yes, it is and for exactly the reason you state: if p is prime then $\left(\begin{array}{c}p \\ i\end{array}\right)$ for p prime and 0< i< p is divisible by p. That itself can be proven directly from the definition: $$\left(\begin{array}{c}p \\ i\end{array}\right)= \frac{p!}{i!(p-i)!}$$ as long as i is neither 0 nor p, 0
 P: 4 What would be the converse of this ^^^? Could you use "the assuming the opposite" method to prove whether or not this holds? cheers
HW Helper
P: 5,346
 Quote by 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
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?

 Related Discussions General Physics 8 Linear & Abstract Algebra 7 Linear & Abstract Algebra 13 Set Theory, Logic, Probability, Statistics 1 General Math 5