Is a proof using modular arithmetic in a question like this valid?

It's been two years or so since I've finished my math undergrad (and I'm doing something non-math related now, unfortunately), so I apologize if what is to follow isn't a very good question!

Prove that for all Integers $n$, $n(n + 1)(2n + 1)$ will always be divisible by 6.

I can do that using induction, but I wanted to try a different way. Does it work to use modular arithmetic in the following way?

Let $f(n) = n(n+1)(2n+1) = 2n^3 + 3n^2 + n$. All we need to show is that $f(n)$ is divisible by both $2$ and $3$ for any choice of $n$.

Evaluate mod $2$.

$f(n) = n(n+1)(2n+1) = n(n+1)(0 + 1)$ mod $2 = n(n+1)$ mod $2$. Two consecutive numbers; one of them must be even, and so $f(n)$ is divisible by $2$.

Evaluate mod $3$

There are three possible residues for n modulo $3$: $0, 1,$ or $2$.

If the residue is $0$, then $f(n)$ is divisible by $3$.

If the residue is $1$, then $f(n) = n(n+1)(2n+1) = 1(1+1)(2*1+1) = 1(2)(3) = 0$ mod $3$.

If the residue is $2$, then $f(n) = 2(2+1)(2*2+1) = 2(3)(2) = 0$ mod $3$.

In any case, $f(n)$ is divisible by $3$.

Since $f(n)$ is divisible by $2$ and by $3$, it is divisible by $6$. The result follows.

Thank you!

Solution 1:

This is a perfectly good argument. In my opinion, solving divisibility problems via modular arithmetic is often a much cleaner approach than using divisibility directly, and this is one such situation.

As an aside, you could convert your mod-3 argument into a "product of three consecutive numbers":

$$ n(n+1)(2n+1) \equiv 2 n(n+1)(n + \frac{1}{2}) \equiv 2 n(n+1)(n+2) \pmod{3} $$

Solution 2:

It's correct, but you can go further.

Fermat’s little theorem

If $p$ is a prime number, then, for every integer $n$, $$n^p\equiv n \pmod{p}$$

There are several proofs. A simple one considers the fact that, if $n$ is coprime with $p$, then $n,2n,3n,\dots,(p-1)n$ are all distinct modulo $p$ and not congruent to $0$, so $$ 1\cdot2\cdot\dots\cdot(p-1)\equiv n\cdot2n\cdot\dots\cdot(p-1)n\pmod{p} $$ which implies $n^{p-1}\equiv1\pmod{p}$. Therefore $n^p\equiv n$, which also holds when $n\equiv0\pmod{p}$.

Modulo $2$

$n(n+1)(2n+1)\equiv n(n+1)\equiv n^2+n\equiv n+n\equiv0\pmod{2}$ because $n^2\equiv n\pmod{2}$ (little Fermat).

Modulo $3$

$n(n+1)(2n+1)\equiv2n^3+3n^2+n\equiv2n^3+n\equiv2n+n\equiv0\pmod{3}$ because $n^3\equiv n\pmod{3}$ (little Fermat).