0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

Hint: Solve $17n \equiv 1 \bmod 100$. Then compute $37^n \bmod 101$ using exponentiation by squaring.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$)? $\endgroup$ – Matthias May 24 at 15:40
  • $\begingroup$ is there another way? For example by using the prime factorization of $100$? $\endgroup$ – Matthias May 24 at 15:43

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