Results 1 to 12 of 12

Math Help - Divisibility

  1. #1
    Senior Member
    Joined
    Jul 2008
    Posts
    347

    Divisibility

    Explain why n^5 - n is divisible by 5 for n=0,1,2,3,....

    Can anyone explain to me how to do this?(without mod - I haven't learnt that)

    Thanx
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Are you sure that's the question?

    I might be doing something wrong but if you put 0 in you get:

    0^5-0=0

    and if you put 1 in you get:

    1^5-1=0

    I don't think 0 is divisible by 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by xwrathbringerx View Post
    Explain why n^5 - n is divisible by 5 for n=0,1,2,3,....

    Can anyone explain to me how to do this?(without mod - I haven't learnt that)

    Thanx
    n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)

    If n=5k : it is divisible by 5.
    If n=5k+1 \implies n-1=5k : it is divisible by 5.
    If n=5k+4 \implies n+1=5k+5=5(k+1) : it is divisible by 5.

    If n=5k+2 \implies n^2+1=(25k^2+20k+4)+1=5(5k^2+4k+1) : it is divisible by 5.
    If n=5k+3 \implies n^2+1=(25k^2+30k+9)+1=25k^2+30k+10=5(5k^2+6k+2) : it is divisible by 5.


    You (or rather I...) have done all the possible situations.


    Quote Originally Posted by Showcase_22
    Are you sure that's the question?

    I might be doing something wrong but if you put 0 in you get:

    0^5-0=0

    and if you put 1 in you get:

    1^5-1=0

    I don't think 0 is divisible by 5.
    yes it is.
    a is divisible by b if when a is divided by b, the quotient is an integer (0 is an integer) and the remainder is 0.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    hmmm....

    I've never thought of it like that before.

    I was trying to use induction on it and I thought it didn't work with 0.

    I'll try it again and post what I get.
    Last edited by Showcase_22; September 11th 2008 at 04:25 AM. Reason: typo.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Moo is on the right track. However, note that

    n^5-n=n(n+1)(n-1)(n^2+1)

    \color{white}.\hspace{10mm}. =n(n+1)(n-1)(n^2-4+5)

    \color{white}.\hspace{10mm}. =n(n+1)(n-1)(n^2-4)+5n(n+1)(n-1)

    Now 5n(n+1)(n-1) is divisible by 5, while n(n+1)(n-1)(n^2-4)=(n-2)(n-1)n(n+1)(n+2) is the product of 5 consecutive integers and so is also divisible by 5; hence their sum is divisible by 5.
    Last edited by JaneBennet; September 11th 2008 at 03:51 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Here's what I did. I think it's right but it would be great if someone could check it. It's been a while since i've done any induction.

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    You did not show that (k-5)(k+1)(k+2)(k^2+2k+2) is divisible by 5 for all k, only that it’s divisible by 5 for k=5. That’s not good enough.

    If you want to use induction, there is no need to factorize. Just use (n+1)^5-(n+1)=(n^5-n)+5(n^4+2n^3+2n^2+n).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    I have to admit that I got a little stuck on that bit.....

    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Yes, you got it.

    Note, however, that you do not say, “Assume true for n=k+1.” You are supposed to prove it is true for n=k+1, not assume it is true.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    I thought that you assumed it was true for n=k+1 and you could only say it is true after you've proven it?

    In this case, I assumed it was true and worked through it. If it wasn't true I wouldn't have ended up with something that was divisible by 5 at the end.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    You don’t assume it is true for n=k+1. In proof by induction, you assume your formula is true for n=k, then prove it is true for n=k+1.

    Be careful what you can and cannot assume in proving something. In proof by contradiction, you assume that the result you want to prove is false, then show that this leads to a contradiction. However, you never assume what you want to prove is already true before proving it. This fallacy is called “begging the question”.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    ahhhh, I get it!

    However, you never assume what you want to prove is already true before proving it. This fallacy is called “begging the question”.
    So I was begging the question when I assumed it was true for n=k+1 ie. I assumed it was true before I had proven it.

    Well I won't make tha mistake again. Thankyou!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum