Proving the congruence $a^3\equiv 0,1,8\pmod{9}$ I'm having some issues solving the following example -
For any positive integer, prove that:
$a^3 \equiv x \space mod \space 9$
where $x = \{0, 1, 8\}$
What I usually do with such examples is attempt and apply mathematical induction and create a gather solution in that way. My approach was something as follows:


*

*$a = 0$ then $0^3 \equiv x \space mod \space$ $(true)$

*$a' = a + 1$ then $a^3 + 3a^2 + 3a + 1 \equiv x \space mod \space 9$
therefore, 


*$(x' \space mod \space 9) \space + a^3 + 3a^2 + 3a + 1 \equiv x \space mod \space 9$
However as the x itself is a set, it does not necessarily have equality in the upper equation (3rd), even though x, and x' consist of same elements in this case (from same set), elements are shifted by +1. Is there any way of proving equivalence with this method or do I need to resort to another one.
If so, what would be the most optimal way of searching for a solution in this case ?
Thank you
 A: Note that $(a+3)^3 = a^3 + 9 a^2 + 27 a + 27 \equiv a^3 \bmod 9$.
Therefore, it's enough to consider $a\in\{0,1,2\}$, in which case it's clear that $a^3 \in \{0,1,8\}$.
More generally, the same argument gives $\{a^p \bmod p^2 : a \in \mathbb Z \} = \{a^p \bmod p^2 : a = 0, \dots, p-1\} $. The key point is the binomial expansion of $(a+p)^p$: all coefficients but the first are multiples of $p^2$.
A: You don't want to do induction here.  
As an alternative you may consider $a$ in $\mod 3$.
That is, consider $3$ cases:  $a = 3k,3k+1, 3k+2$,
 and in each case look at the remainder $a^3\mod 9$.
A: By below: $\ \overbrace{a\equiv 0,\pm1\pmod{\!3}}^{\rm Division\ Algorithm}\,\Rightarrow\,a^{\large 3}\equiv [0,\pm1]^{\large 3}\equiv 0,\pm1\pmod{\!3^{\large 2}}$
Lemma $\,\ \ \ a\ \equiv\ b\ \ \pmod{ n}\ \Rightarrow\ a^{\large n}\, \equiv\ b^{\large n}\ \pmod{\!n^{\large 2}}$
Proof $\ $ By hypothesis $\ a = b\!+\!nj\,$ for some integer $\,j\,$ so by the Binomial Theorem
 $$  a^{\large n} = (b\!+\!nj)^{\large n}\! = b^{\large n}\! + \color{#c00}n(\color{#c00}nj)\, b^{\large n-1}\! + (\color{#c00}nj)^{\large\color{#c00} 2}(\cdots) \equiv b^{\large n}\!\! \pmod{\!\color{#c00}{n^{\large 2}}}\qquad\qquad$$
Remark $ $ It is worth the slight extra effort to prove the general lemma above (vs. OP special case) since it often proves handy in number theory.
A: In addition to ganeshie8's answer, you can instead consider the cases $3k-1$, $3k$ and $3k+1$. Then using the binomial theorem, it is obvious that this evaluates to $-1$, $0$ and $1$ modulo $3$.
