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
Scientists develop 'electronic nose' for rapid detection of C. diff infection
Why plants in the office make us more productive
Tesla Motors dealing as states play factory poker
mathman
#2
Jul20-08, 03:21 PM
Sci Advisor
P: 6,076
(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,557
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,557
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