Show that for every integer $n$, $n^3 - n$ is divisible by 3 using modular arithmetic

Problem:

Show that for every integer $n$, $n^3 - n$ is divisible by 3 using modular arithmetic

I was also given a hint:

$$n \equiv 0 \pmod3\\n \equiv 1 \pmod3\\n \equiv 2 \pmod3$$

But I'm still not sure how that relates to the question.

Answer

Using the hint is to try the three cases:

Case 1: $n \equiv 0 \mod 3$

Remember if $a \equiv b \mod n$ then $a^m \equiv b^m \mod n$ [$*$]

So $n^3 \equiv 0^3 \equiv 0 \mod 3$

Remember if $a \equiv c \mod n$ and $b \equiv d \mod n$ then $a+b \equiv c + d \mod n$ [$**$]

So $n^3 - n\equiv 0 - 0 \equiv 0 \mod n$.

Case 2: $n \equiv 1 \mod 3$

Then $n^3 \equiv 1^3 \mod 3$ and $n^3 - n \equiv 1^3 - 1 \equiv 0 \mod n$.

Case 3: $n \equiv 2 \mod 3$

Then $n^3 \equiv 2^3 \equiv 8 \equiv 2 \mod 3$.

So $n^3 - n \equiv 2- 2 \equiv 0 \mod 3$.

So in either of these three cases (and there are no other possible cases [$***$]) we have $n^3 - n \equiv 0 \mod 3$.

That means $3\mid n^3 - n$ (because $n^3 - n \equiv 0 \mod 3$ means there is an intger $k$ so that $n^3 - n = 3k + 0 = 3k$.)

---

I find that if I am new to modulo notation and I haven't developed the "faith" I like to write it out in terms I do have "faith":

Let $n = 3k + r$ where $r = 0, 1$ or $2$

Then $n^3 - n = (3k+r)^3 -(3k+r) = r^3 - r + 3M$

where $M = [27k^3 + 27k^2r + 9kr^2 - 3k]/3$ (I don't actually have to figure out what $M$ is... I just have to know that $M$ is some combination of powers of $3k$ and those must be some multiple of $3$. In other words, the $r$s are the only things that aren't a multiple of three, so they are the only terms that matter. )

and $r^3 -r$ is either $0 - 0$ or $1 - 1 = 0$ or $8 - 2 = 6$. So in every event $n^3 - n$ is divisible by $3$.

That really is the exact same thing that the $n^3 - n^2 \equiv 0 \mod 3$ notation means.

---

[$*$] $a\equiv b \mod n$ means there is an integer $k$ so that $a = kn + b$ so $a^m = (kn + b)^m = b^m + \sum c_ik^in^ib^{m-i} = b^m + n\sum c_ik^{i}n^{i-1} b^{m-i}$. So $a^m \equiv b^m \mod n$.

[$**$] $a\equiv c \mod n$ means $a= kn + c$ and $b\equiv d \mod n$ means $b = jn + d$ for some integers $j,k$. So $a + b = c+ d + n(j+k)$. So $a+b =c + d \mod n$.

[$***$]. For any integer $n$ there are unique integers $q, r$ such that $n = 3q + r ; 0 \le r < 3$. Basically this means "If you divide $n$ by $3$ you will get a quotient $q$ and a remainder $r$; $r$ is either $0,1$ or $2$".

In other words for any integer $n$ then $n \equiv r \mod 3$ where $r$ is either $0,1,$ or $2$. These are the only three cases.

---

P.S. That is how I interpretted the hint. As other have pointed out, a (arguably) more elegant proof is to note $n^3 - n = (n-1)n(n+1)$ For any value of $n$ one of those three, $n$, $n-1$, or $n+1$ must be divisible by $3$.

This actually proves $n^3 - n$ is divisible by $6$ as one of $n$, $n-1$ or $n+1$ must be divisible by $2$.

---

There is also induction. As $(n+ 1)^3 - (n+1) = n^3 - n + 3n^2 + 3n$, this is true for $n+1)$ if it is true for $n$. As it is true for $0^3 - 0 = 0$ it is true for all $n$.