Inverse Modular Arithmetic

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.

2 Answers

$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}$.

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$.

• The question I'm asking actually preceded by another question which is to find the inverse of 11 mod 40, the answer is 11. Does it has anything to do with this? What I understand from what you read is I need to find n that is coprime with 41. I actually have figured out the question and got x = 10, the expression I'm looking for is $10^11 \mod 41$, but I'm just completely lost how to get to there. How to get from $x = 10^{1/11} \mod 41$ to $x = 10^{11} \mod 41$. @AAA Commented Jan 15, 2015 at 0:06
• @Stud you could certainly solve that question using a generator / log table, but there's ways to solve that more directly. Commented Jan 15, 2015 at 0:09
• Mind to elaborate the faster way to directly solve it? @AAA Commented Jan 15, 2015 at 0:21
• @Stud Finding an inverse is just solving a linear diophantine equation $ax+by=1$, which you do using Euclid's division algorithm. Commented Jan 15, 2015 at 0:46