2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.