Easy way to compute $k^{20}=1\pmod{101}$? I know that it is assumed hard to calculate the opposite ($20^k$), basically the discrete log problem. I also know that is easy to verify for some $k$ whether $k^{20}=1\pmod{101}$ holds. Solutions are 1, 6, 10, 14, 17, ... However, is there an easy way to directly compute these values for say $1 < k < 100$?
 A: Well, $101$ is a prime, so the group $\mathbb{Z}_{101}^*$ is cyclic of order $100$. Therefore anything coprime to $101$ raised to $100$ gives you something congruent to $1$ modulo $101$ (also known as Little Fermat). Therefore
$$
k=a^5
$$
is a solution to the congruence $k^{20}\equiv1\pmod{101}$ for all integers $a$ coprime to $101$. Proof:
$$
k^{20}=(a^5)^{20}=a^{100}\equiv1\pmod{101}.
$$
So $a=1$ gives $k=1$, $a=2$ gives $k=32$, $a=3$ gives $k=243=41$ et cetera.
It also follows from basic properties of cyclic groups that you get all the solutions (up to congruence) in this way.

Addition (in response to a useful exchange of comments with N.S. and TonyK):
We know that there are exactly 20 non-congruent solutions. Furthermore, the solutions form a subgroup. Let's check out the order of the first solution $k=32$ we found with $a=2$. We have $k^2=1024=14$, $k^4=196=-6$, so $k^5=-192=10$. This implies that $k^{10}=100=-1$. Therefore $k=32$ cannot be of order that is a factor of either $4$ or $10$, so its order is $20$ and we're done. If we had gotten less than 20 solutions with this $k$ we would have tried another value of $a$ and checked out whether that helps. This algorithm ends at least as fast as systematically searching for a primitive root.
A: Short of finding a primitive root: By trial and error, you find e.g. $6$. Then the powers of $6$ are also roots. Unfortunately, that gives only ten solutions, so we have missed some solutions.
We find another solution, e.g. $10$ either by trial and error or by recognizing that $101=10^2+1$. Then multiplying the previously found ten solutions by $10$ gives the remaining ten roots.
