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).
Related posts:
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