# Show that $x^3 \equiv 0,1,8 \mod{9}$ (Critique my solution)

My solution is based on the idea that it is sufficient to consider the cubes less than 9. Ie $0^3 \equiv 0, 1^3\equiv 1, 2^3 \equiv 8$. Since these are the only cubes in the residue class$\mod{9}$ these are the only possibilities for $x^3 \mod{9}$

Is this a sufficient motivation?

New solution:

By computation, $0^3 \equiv 3^3 \equiv 6^3 \equiv 0 \mod{9}$ and $1^3 \equiv 4^3 \equiv 7^3 \equiv 1 \mod{9}$ and $2^3 \equiv 5^3 \equiv 8^3 \equiv 8 \mod{9}$. For any $x$, we can can calculate $x^3\mod{9}$ by reducing $x \equiv y \mod{9}$ where $0 \leq y \leq 8$ , and so $x^3 \equiv y^3 \mod 9$ where $y^3$ is one of our cases above, ie either 0,1 or 8.

• Hint. Instead of "cubes less than 9" consider "cubes of numbers less than 9". You can save yourself a little arithmetic by cubing the numbers between -4 and 4 instead. Oct 8 '16 at 13:29
• @ethan-bolker Thanks! I updated my solution with a new approach. Oct 8 '16 at 13:52

According to that reasoning, since $1^3\equiv1,2^3\equiv8,3^3\equiv0\pmod{27}$, we have that $x^3\equiv0,1,8\pmod{27}$ for any $x$. But $4^3\equiv10\pmod{27}$.
• The Euler's Totient function $\varphi$ (and the Carmichael function) are somewhat related to this. For example, one may prove that if $\varphi(n)$ is not multiple of $3$, then $x^3\bmod n$ can be any of $\{0,1,2,\dots,n-1\}$. On the other hand, when $\varphi(n)$ is multiple of $3$, this is not true. (In your example, $\varphi(9)=6$.) Oct 8 '16 at 13:36