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

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
 PhysOrg.com science news on PhysOrg.com >> City-life changes blackbird personalities, study shows>> Origins of 'The Hoff' crab revealed (w/ Video)>> Older males make better fathers: Mature male beetles work harder, care less about female infidelity
 Recognitions: Science Advisor (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.
 Recognitions: Gold Member Science Advisor Staff Emeritus 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.

## 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).
 Recognitions: Gold Member Science Advisor Staff Emeritus 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
 What would be the converse of this ^^^? Could you use "the assuming the opposite" method to prove whether or not this holds? cheers

Recognitions:
Homework Help
 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?

 Similar discussions for: prove (n^5 - n) is divisible by 5 by induction Thread Forum Replies General Physics 8 Linear & Abstract Algebra 7 Linear & Abstract Algebra 13 Set Theory, Logic, Probability, Statistics 1 General Math 5