Why are there no impossible modular residues of cubes for some moduli?

Question

I was working on a problem about cubes but I kept on getting stuck on some cases because for some moduli, for example 10, there are no impossible residues. For modulo 10:

\begin{array} .N & N^3\pmod{10} \\\hline 1 & \hfill 1 \hfill\\ 2 & \hfill 8 \hfill\\ 3 & \hfill 7 \hfill\\ 4 & \hfill 4 \hfill\\ 5 & \hfill 5 \hfill\\ 6 & \hfill 6 \hfill\\ 7 & \hfill 3 \hfill\\ 8 & \hfill 2 \hfill\\ 9 & \hfill 9 \hfill\\ 0 & \hfill 0 \hfill \end{array}

All the residues are used in the $N^3\pmod{10}$ table. Also for modulo $7$ all cubes are congruent to either $1$ or $-$1 modulo $7$. My question is whether there is a mathematical reason for why this is the case. Thanks

Answer 1

Yes, there is a mathematical reason. It's easiest to understand for prime moduli. Primes other than $3$ leave a remainder of $1$ or $2$ when you divide by $3$. Work out your tables for $p=5,7,11,13,17,19$ and you should see the pattern.

Fermat's Little Theorem will help you with a proof.

You can read about this at the beginning of the wikipedia page on cubic residues.

Answer 2

Yes, $\bmod 10\,$ the cube map $\,c(n) = n^3$ is a bijection by $\, a \equiv a^9 = (a^3)^3 = c(c(a))\,$ therefore $\,c\,$ is self-inverse. Indeed $\,a^9\equiv a\pmod{\!10}\,$ follows by a slight generalization of little Fermat / Euler.

You can observe this in your table: $\,2\mapsto 8\mapsto 2,\,$ $\, 3\mapsto 7\mapsto 3\,$ and others are fixed points so $\,c(c(a)) = a,\,$ i.e. $\,c^2 = 1,\,$ so $\,c^{-1} = c,\,$ i.e. $\,c\,$ is the permutation $\,(2\ 8)\,(3\ 7)\,$ in cycle notation.

More generally if $\,n\,$ is a product of distinct primes $\equiv 2\pmod{\!3}\,$ then $\,\phi = \phi(n)\equiv 1\pmod{\!3}.\,$ Hence $\bmod 3\!:\ \phi\equiv 1\,\Rightarrow\,2\phi+1\equiv 0\,$ so $\,\color{#c00}{2\phi+1 = 3k}\,$ so the above linked theorem yields

$$\bmod n\!:\,\ 0\equiv a(a^{2\phi}-1)\,\Rightarrow\,a\equiv (a^{\large\color{#c00}k})^{\large 3}\equiv a^{\large \color{#c00}{2\phi+1}} \qquad\qquad\!\!\!$$

e.g. $\, \begin{align} n &= 2\cdot 5\cdot 11 = 110\\ \phi &= 1\cdot 4\cdot 10 = 40\end{align}\ $ so $\,2\phi+1 = 27\cdot 3\ $ so $\ a\equiv (a^{\large 27})^{\large 3}\pmod{\!110}$

When $\,n\,$ is a prime $\equiv 2\pmod{\!3}\,$ the above specializes to a simple case of cubic reciprocity.

---

For the 2nd question, by Fermat, $\!\bmod 7\!:\ n\not\equiv 0\,\Rightarrow 0\equiv n^6-1 = (n^3-1)(n^3+1)$ so $7$ divides one of the factors by Euclid's Lemma, so $\,n^3\equiv \pm1.\,$ More generally see Euler's Criterion.