# How to solve $x^{17}\equiv 37$ in $\mathbb{Z}/101\mathbb{Z}$? [duplicate]

I need to solve the equation $$x^{17}\equiv 37$$ in $$\mathbb{Z}/101\mathbb{Z}$$.

I've looked into these topics (the calculation of the primitive root is missing, n is not prime) but couldn't derive a solution.

So summarize what I know:

1. 101 is prime $$\implies \mathbb{Z}/101\mathbb{Z}$$ is cyclic group (or even a field)
2. since $$\mathbb{Z}/101\mathbb{Z}$$ is cyclic it has a generator with the same order of $$\mathbb{Z}/101\mathbb{Z}$$. In this case the generator has order $$\phi(101)=101-1=100$$
3. due to Fermat I have $$x^{100}\equiv 1$$ $$mod(101)$$
4. $$\phi(101)=100=2^2\cdot 5^2$$
5. I have tried in vain to orient myself to: $$n-th$$ root at the bottom of the page
6. I know that the (only) solution is $$x=52$$

Can somebody help me?

Hint: Solve $$17n \equiv 1 \bmod 100$$. Then compute $$37^n \bmod 101$$ using exponentiation by squaring.
• thanks. $17n\equiv 1$ $\text{mod 100} \implies n=53$. But how to calculate $37^{53} \text{ mod 101}$ by hand? Could you pls explain why your hint follows to the right result (which is indeed $x=52$)? – Matthias May 24 at 15:40
• is there another way? For example by using the prime factorization of $100$? – Matthias May 24 at 15:43