### Divisibility of N(N+1)(2N+1) by 6

Jeffrey Samuelson twitted a question to which I am happy to provide an answer, or two.

### Question

Find an integer N such that N(N+1)(2N+1) is NOT divisible by 6. If no such integer exists, prove why.

Since the question is about the properties of a product modulo 6, it seems proper to investigate the dependency of the product on the residues modulo 6. Let's form a table

N | N+1 | 2N+1 | |
---|---|---|---|

0(6) | 1 | 1 | |

1 | 2(2) | 3(3) | |

2(2) | 3(3) | 5 | |

3(3) | 4(2) | 1 | |

4(2) | 5 | 3(3) | |

5 | 6(6) | 5 |

The first number in a cell is the remainder of division by 6 of the number in the caption of a column. The number in parentheses - if present - shows a factor of that number. Clearely, in every row, the product of factors is at least 6. So that, for every possible value of N modulo 6, the product N(N+1)(2N+1) is divisible by 6.

An effort of putting together a table could have been spared with an observation that, for every integer N,

N(N+1)(N+2) is divisible by 6

In words, *a product of any three consecutive integers is divisible by 6.* This is a somewhat simpler variant of the problem at hand. Why a variant? Are not problems rather different? Yes and no. Consider the difference

N(N+1)(2N+1) - N(N+1)(N+2) = N(N+1)(N-1) = (N-1)N(N+1).

Or, separating N(N+1)(2N+1),

N(N+1)(2N+1) = N(N+1)(N-1) = (N-1)N(N+1) + N(N+1)(N+2),

meaning that N(N+1)(2N+1) is the sum of two products of three consecutive integers, each of which is divisible by 6.

Finally, N(N+1)(2N+1)/6 is the sum of the first N squares: 1² + 2² + ... + N² (see, Jeff's derivation. This is called a *combinatorial* argument. Since N(N+1)(2N+1)/6 is thus an integer, 6 is bound to be a factor of N(N+1)(2N+1).

Thanks for the insights into the problem! I do appreciate it. Your site is a fantastic mathematics resource!

April 8th, 2011 at 8:23 amJeff, you questions are a real inspiration. Thinking of a problem, turning it in your head after getting a solution - looking back - is the way to learn how to do mathematics. You are on the right track ...

April 12th, 2011 at 8:09 amTerm is divisible by 6 if divisible by 2 and 3.

April 24th, 2011 at 7:02 pmTerm is divisible by 2 (N or N+1 are even).

Term is divisible by 3 by putting N=3k, N=3k+1, N=3k-1.

Yes, this will also work.

April 25th, 2011 at 7:46 am