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

Proof by div alg.

  1. Jul 21, 2012 #1
    How can i prove that if n>=1, (n(n+1)(2n+1))/6 is an integer. The hint is to use the division algorithm such that n has one of the forms 6k,6k+1,..6k+5 and to work each case.......I tried changing n to 6k but i failed immeaditely :(
     
  2. jcsd
  3. Jul 21, 2012 #2

    Check that no matter what natural [itex]\,n\,[/itex] is, the number [itex]\,(n)(n+1)(2n+1)\,[/itex] is always divisible both by 2 and 3.

    DonAntonio
     
  4. Jul 21, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Looking at n "modulo 6" seems an awkward way of doing this. Looking at "modulo 2" and "modulo 3" separately is far easier.

    Specifically, of any two consectutive numbers, such as n and n+1, one of them must be even. Now, n must be of the form 3k (a multiple of 3), 3k+1, or 3k+ 2. If n is a multiple of 3 then we have factors of both 3 and 2 in the product and so the product is divisible by 6. If n= 3k+2, then n+ 1= 3k+2+1= 3k+ 3= 3(k+1) so n+1 is a multiple of 3. If n= 3k+1, then 2n+ 1= 6k+ 2+ 1= 6k+ 3= 3(2k+1).

    But since you specifically say "6k, 6k+ 1" etc.:

    If n= 6k the n itself is divisible by 6 so the product is.

    If n= 6k+ 1 then n+ 1= 6k+ 2= 2(3k+1) so n+ 1 is divisible by 2 and 2n+ 1= 12k+ 2+ 1= 12k+3= 3(3k+ 1) is a multiple of 3 so the product of n and 2n+1 is divisible by 6.

    If n= 6k+ 2= 2(3k+1), n is divisible by 2. n+1= 6k+ 2+1= 6k+3= 3(2k+1) so n+1 is divisible by 3 and the product of n and n+1 is divisible by 6.

    If n= 6k+ 3= 3(2k+1), n is divisible by 3. n+ 1= 6k+ 3+ 1= 6k+ 4= 2(3k+ 2) so n+ 1 is divisible by 2 and the product of n and n+1 is divisible by 6.

    If n= 6k+ 4= 2(3k+ 2), n is divisible by 2. 2n+1= 12k+ 8+ 1= 12k+ 9= 3(4k+ 3) so n+1 is divisible by 3 and the product of n and n+1 is divisible by 6.

    If n= 6k+ 5, n+ 1= 6k+ 6= 6(k+ 1) is divisible by 6.
     
  5. Jul 22, 2012 #4
    Thanks DonAntonio, thats a very good clue which i did not think about. :)
     
  6. Jul 22, 2012 #5
    Thanks HallsofIvy, youve made my work very easy now. :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof by div alg.
  1. Euclidean alg (Replies: 8)

  2. A proof (Replies: 1)

  3. Simple Ab Alge proof (Replies: 6)

Loading...