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. 
 A: Note that $n^{3} - n = n(n^2 - 1) = n(n+1)(n-1)$. Now treat three cases: $n$ is either congruent to $0,1$, or $2$ mod $3$.
A: First, factor $n^3 -n$
$$n^3-n = n(n-1)(n+1)$$
From here, we have shown that $n^3-n$ is the product of three consecutive integers. In any one set of three consecutive integers, there is one factor of $3$ because one of the numbers is congruent to $0$, another to $1$, and the last to $2 \bmod 3$
Alternatively, we can start from the back and go casewise:
Case 1:$$ n\equiv 0 \mod 3$$
$$n^3 - n \equiv 0^3 - 0 \equiv 0 \mod 3$$
Case 2:
$$n \equiv 1 \mod 3$$
$$n^3 -n \equiv 1^3 - 1 \equiv 1-1 \equiv 0\mod 3$$
Case 3:
$$n \equiv 2 \mod3$$
$$2^3 - 2 \equiv 8-2 \equiv 6 \equiv 0\mod 3$$
Since these cases are exhaustive, we are done.
A: The hint is telling you that you have only three cases to check. Here are the details for this first two cases, I leave the third case for you to finish off:


*

*If $n \equiv 0\pmod 3$, then $n^3 - n \equiv  0^3 - 0 \equiv 0 \pmod 3$

*If $n \equiv 1\pmod 3$, then $n^3 - n \equiv 1^3 - 1 \equiv 0 \pmod 3$

*If $n \equiv 2\pmod 3$, then $n^3 - n \equiv 2^3 - 2 \equiv \ldots$


The fact that you are using here is that reduction modulo $n$ is a homomorphism, i.e., it respects addition and multiplication.
A: 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$.
