# Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$

Prove that if a $\in \mathbb{Z}$ then $a^{3} \equiv a(mod 3)$

So, the ways I have learned (or am learning, rather) to do proofs is using direct, contrapositive and contradiction.

So, I started it using direct, and got this:

$n|(a^{3}-a)$

Then there exists an integer k such that:

$nk = a^{3} - a$

$nk = a(a^{2} - 1)$

$nk = a(a+1)(a-1)$

so a must be -1, 0 or 1.

And there is where I'm stuck. I don't know where to go next and I'm not sure if it would be easier to use another method, maybe contradiction? Any help is appreciated! Thanks.

• See my answer below. How many factors are there? What is their relationship to each other? – user4894 Oct 26 '14 at 19:21

Try factoring $a^3−a$. What do you notice about the relationship of the factors to each other? How many are there? What can you then conclude?

• – user1282637 Oct 26 '14 at 19:46
• Comments are not for extended discussion; this conversation has been moved to chat. – user642796 Oct 27 '14 at 5:31

The other answers are great. You can also break this into cases. For any integer $a$, we must have:

$a \equiv \text{0, 1, or 2} \pmod{3}$.

Considering each case, we have:

$$0^3 \equiv 0 \pmod{3}$$ $$1^3 \equiv 1 \pmod{3}$$ $$2^3 \equiv 8 \equiv 2 \pmod{3}$$

More generally, I'd recommend reading up on Fermat's Little Theorem.