Proving the congruence $a^3\equiv 0,1,8\pmod{9}$

Question

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:

1. $a = 0$ then $0^3 \equiv x \space mod \space$ $(true)$
2. $a' = a + 1$ then $a^3 + 3a^2 + 3a + 1 \equiv x \space mod \space 9$

therefore,

3. $(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

Answer 1

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$.

Answer 2

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$.

Answer 3

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$.

Answer 4

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.