Inverse Modular Arithmetic

Question

or example I have this expression: $x^{11} \mod 41 = 10$

I need to find the value of x, never mind about the process of getting the answer.

What I need to know is how do I find the inverse of the expression?
I assume it would be something along the line $x = 10^{1/11} \mod 41$ if it is, how simplify the exponent? How can I get rid of it so I can work with integer exponent?

Thank you.

Answer 1

$41$ is a prime number, so we know that, for $x\not\equiv0\pmod{41}$, $x^{40}\equiv1\pmod{41}$ (Fermat's little theorem).

Since $11$ is prime with $40$, we know there are $a$ and $b$ such that $11a+40b=1$: take $a=11$ and $b=-3$. Thus we see that $$ (x^{11})^{11}=x^{121}=x^{3\cdot 40+1}\equiv x\pmod{41} $$ So, if $x^{11}\equiv 10\pmod{41}$, we also have $$ x\equiv 10^{11}\pmod{41} $$ It's not hard to see that $10^{11}\equiv 10\pmod{41}$.

Answer 2

Hint: find a generator in the unit group, that is, an element $u$ with $u^{40} = 1$ and $u^n = 1$ for no smaller positive number $n$ than $40$. To do this, find units with orders whose g.c.d. is $\phi(41) = 40$.