Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that n^3-n is divisible by 6 for every integer n

  1. Sep 16, 2005 #1
    Prove that n^3-n is divisible by 6 for every integer n. Is it induction to be used here?...
     
  2. jcsd
  3. Sep 16, 2005 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    n3-n= n(n2-1)= n(n-1)(n+1)= (n-1)(n)(n+1), three consecutive integers. What does that tell you?
     
  4. Sep 16, 2005 #3
    Oh, My!...shame on me!
    Now that I submitted this thread and can't delete it:
    Is it generally right?:
    If 6 divides n^3-n then, since divisibility is transitive and 2 divides 6 , 2 must also divide n^3-n. Let n be even then n^3 is even and n^3-n is also even. Let n be odd then n^3 is odd and hence n^3-n is even. Since every even number is divisible by 2 it follows that 6 divides n^3-n.
     
  5. Sep 16, 2005 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You're going at this backwards assuming 6 divides n^3-n then showing 2 divides it?

    You've managed to show 2 divides n^3-n by considering n even or odd, but to show 6 divides n^3-n you need to also show 3 divides n^3-n. Consider Hall's factorization, can you show 3 divides (n-1)n(n+1) for any n?
     
  6. Sep 16, 2005 #5
    Oh sorry, thanks, HallsofIvy, you seem to have won the race!...posted a few minutes earlier...I didn't see it. :)

    oh that was even more easier! nice...that n^3-n is always even?...
     
  7. Sep 16, 2005 #6
    ...now that was my problem...how can I show that 3 divides n^3-n?...I need to show that the sum of the digits is divisible by 3...but the number is encoded in a formula!...so what can I do?

    I dont have an idea of the Hall's factorization...could you tell me more about it or post me a link to a resource?

    well, this is a problem at the very beginning of Nathanson's Elementary Methods in Number Theory, which I've just started reading....since I have no idea of number theory. It actually has no prerequisites for this problem except transitivity, division algorithm and induction principle...well there is also a theorem about an m-adic representation of numbers...but I dont think it needs to be used here...
     
  8. Sep 16, 2005 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Here's how you could show n^3-n is divisible by 2 using Hall's factorization:

    n^3-n=(n-1)n(n+1). So for any n, we must have both n-1 and n dividing n^3-n. n-1 and n are consequetive integers, hence one of them is divisible by 2. Therefore n^3-n is divisible by 2.

    Does this give you any ideas on how to handle the 3 case?
     
  9. Sep 16, 2005 #8
    Great!...Can I generalise it by saying that among any n successive integers there is exactly one divisible by n?...What is a formal proof for this?
     
  10. Sep 16, 2005 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    That's correct. n successive integers starting at m look like m, m+1, ..., m+n-1. Use the division algorithm to write m=n*q+r, where 0<r<=n (note I've changed r slightly from the usual form). Then m+n-r is divisible by n and 0<=n-r<n so m+n-r is one of m, m+1, ..., m+n-1
     
  11. Sep 16, 2005 #10
    OK, but why did you change r?...It's 0<=r<=n-1, is it?...which gives 1<=n-r<=n and not 0<=n-r<n...cant get it. °_°
     
  12. Sep 16, 2005 #11
    ...and doesnt that mean that m+1,...,m+n-1 are all divisible by n?
     
  13. Sep 16, 2005 #12

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Because it worked with the sequence I had already typed and seemed easier than going back to modify it. If you believe the division algorithm will give you an r with 0<=r<n you should be able to wrangle this to a different r with 0<r<=n, there's little difference.

    Or you could change the consecutive numbers to m+1, m+2, ... m+n
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Prove that n^3-n is divisible by 6 for every integer n
  1. Divisibility of n by 6 (Replies: 10)

Loading...