Solution

Show that if $a$ is an integer, then 3 divides $a^3-a$.


Consider the factorization below: $$\begin{align}a^3-a &= a(a^2-1)\\ &= a(a+1)(a-1)\\ &= (a-1) \cdot a \cdot (a+1)\end{align}$$ Note, when written in this last form, it is easy to see that when $a$ is an integer, $a^3-a$ is the product of three consecutive integers. One of these three integers must be divisible by 3, which then makes their product divisible by 3. More precisely:

  • If $a$ divided by 3 leaves a remainder of 0, then $3 \mid a$.
  • If $a$ divided by 3 leaves a remainder of 1, then $3 \mid a - 1$.
  • If $a$ divided by 3 leaves a remainder of 2, then $3 \mid a + 1$.

These are the only possible remainders that can be left upon division by 3. As such, regardless of the value of the integer $a$, 3 always divides one of the factors in $a(a-1)(a+1)$, and hence, $3 \mid a^3 - a$ for any integer $a$.