Register to reply

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

by Fizza
Tags: divisible, induction, prove
Share this thread:
Fizza
#1
Jul20-08, 02:22 PM
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
Phys.Org News Partner Science news on Phys.org
Mysterious source of ozone-depleting chemical baffles NASA
Water leads to chemical that gunks up biofuels production
How lizards regenerate their tails: Researchers discover genetic 'recipe'
mathman
#2
Jul20-08, 03:21 PM
Sci Advisor
P: 6,057
(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
#3
Jul21-08, 01:48 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,491
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.

dodo
#4
Jul21-08, 03:09 AM
P: 688
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).
HallsofIvy
#5
Jul21-08, 08:13 AM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,491
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 [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 np- n is divisible by p, do exactly what mathman suggested.

First, when n= 1, 1p- 1= 0 which is divisible by p. Now assume the statement is true for some k: kp- 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 kp so we have kp- k= mp. The other terms, all with 0< i< p, contain, as above, factors of p.
googlymunja32
#6
Aug16-08, 01:50 PM
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
LowlyPion
#7
Aug16-08, 06:27 PM
HW Helper
P: 5,341
Quote Quote by Fizza View Post
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?


Register to reply

Related Discussions
Infinitely divisible vs finitely divisible time General Physics 8
Prove that phi(a^n - 1) is divisible by n Linear & Abstract Algebra 7
Prove a^2 + b^2 = 3(s^2 + t^2) implies both a and b must are divisible by 3 Linear & Abstract Algebra 13
Prove by induction? Set Theory, Logic, Probability, Statistics 1
Prove that n^5 - 5n^3 + 4n is divisible by 120: General Math 5