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

  1. here's what Ive done so far...

    P(n) = n^5 - n
    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
  2. jcsd
  3. mathman

    mathman 6,754
    Science Advisor
    Gold Member

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

    HallsofIvy 41,265
    Staff Emeritus
    Science Advisor

    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.
  5. 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).
  6. HallsofIvy

    HallsofIvy 41,265
    Staff Emeritus
    Science Advisor

    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.
    Last edited: Jul 21, 2008
  7. Hello hall of Ivy

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

  8. LowlyPion

    LowlyPion 5,324
    Homework Helper

    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?
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Prove (n^5 - n) is divisible by 5 by induction