Show that the congruence $x^3\equiv a \pmod {167}$ has solutions for all a.

Question

I cam across this question, and don't really know how to get started:

Show that the congruence $x^3\equiv a \pmod {167}$ has solutions for all a.

I have benn studying about primitive roots for the last couple of weeks, but I don't see any connection to this question. I would like to get some hints.

Answer 1

Hint: Note that $\gcd(3, \varphi(167)) = 1$ and use Euler's theorem.

Answer 2

We have to show that for $$x\ne y\mod 167$$ we have $$x^3\ne y^3\mod 167$$ Suppose $x^3\equiv y^3\mod 167$ Then, we have $$x^{168}\equiv y^{168}\mod 167$$ and we also have $$x^{167}\equiv y^{167}\equiv 1\mod 167$$ unless $167|x$ or $167|y$, in which case we get $x\equiv y\equiv 0\mod 167$. So, we get $x\equiv x^{168}\equiv y^{168}\equiv y\mod 167$ , completing the proof.

Answer 3

We have $1 = (-55)\cdot 3 + 166$ and so $$ a = a^1 = a^{(-55)\cdot 3 + 166} = a^{(-55)\cdot 3} a^{166} \equiv (a^{-55})^3 \cdot 1 \equiv (a^{166-55})^3 = (a^{111})^3 \bmod 167 $$

More generally, in a finite cyclic group of order $n$, the map $x \mapsto x^m$ is surjective (and so a bijection) iff $\gcd(m,n)=1$. The proof is like the one above, applied to a generator of the group. Once you know that a generator is an $m$-th power, then so is every element in the group.

That's the connection with primitive roots. Here is a one-line proof along these lines. Let $g$ be a primitive root mod $167$. Then $(g^{111})^3=g^{333} = g^{333 \bmod 166} = g^1 = g$.