Given $x^5 \equiv 2 \pmod {2011},$ I need to solve for $x$ How can I solve this equation?:
$$x^5 \equiv 2 \pmod{2011},\quad x \in \mathbb{N}$$
I mean, I don't see how can I solve it without using a computer...
 A: You do not have to trial multiple exponents.
Begin by verifying that $2$ is a fifth power residue $\bmod 2011$.  This is done by showing that $2^{402}\equiv 1$ (all equivalence are understood here to be $\bmod 2011$).  Having certified that, conclude that
$2^{402m+1}\equiv 2$
For any whole number $m $.  But then the exponent $402m+1$ is a multiple of $5$ for $m=2$ leading to:
$2^{805}=(2^{161})^5\equiv 2$
so that  $x=2^{161}\equiv 1525$ is identified as one solution.
The other solutions are obtained from multiplication by a primitive fifth root of unity.  This would be any $402$nd power of a non-fifth power residue.  We have seen that $2$ is a fifth-power residue, but $3$ gives : $3^{402}\equiv 1328$.  Thus the solution is completed by successive multiplication of $1525$ by  $1328$.  After sorting the complete solution set is given by
$\{123, 295, 453, 1525, 1626\} $
A: Without a computer it's a lot of work. (But I'd love to see a clever solution!)
The main point is that $2011$ is a prime and so the multiplicative group mod $2011$ is cyclic.
Thus, first you need to find a primitive root mod $2011$. There is usually a small one.
$2$ has order $402$ and so is not a primitive root, but $g=3$ is a primitive root.
If $a$ is a root of $x^5=2$, then all roots are of the form $au$, with $u^5=1$. The elements of order $5$ are $g^{402k}$ for $k=1,\dots,4$ and so $u=g^{402k}$ for $k=0,\dots,4$.
Therefore, you only need to find one root of $x^5=2$, which can be done by testing the powers of $g^5$; these contain the elements of order $402$. (You only have to test exponents coprime with $402=2 \cdot 3 \cdot 67$, still $132$ exponents.)
