1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...