Proof by div alg.

MAGICMATHS

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 :(

DonAntonio

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

HallsofIvy

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.

MAGICMATHS

Thanks DonAntonio, thats a very good clue which i did not think about. :)

MAGICMATHS

Thanks HallsofIvy, youve made my work very easy now. :)