How do you go about solving $x^{11} \equiv 5 \pmod{41}$. I'm very new to this topic and have watched numerous YouTube tutorials with not much luck so far.
Thanks in advance.
Asked
Active
Viewed 535 times
1
-
2Find $k$ so that $11\cdot k \equiv 1 \pmod{40}$. And think of Fermat's theorem. – Daniel Fischer Mar 06 '16 at 19:59
1 Answers
1
Expanding on @DanielFischer 's comment. Since $41$ is prime, one knows that $x^{41}\equiv x\pmod{41}$ via Fermat's little theorem. Now, you know that $5^{41}\equiv 5\mod 41$.
Our job is now to rewrite $5^{41}$ as $x^{11}$. Since $5^{40}\equiv 1\pmod{41}$ by Fermat's little theorem, we wish to find a $k$ so that $(5^{40})^k5^{41}$ is of the form $x^{11}$. In other words, you want to find a $k$ so that the exponent of $5^{40k+41}$ is a multiple of $11$.
Therefore, you will solve $40k+41\equiv 0\pmod{11}$. Once you have that $k$, you know that $40k+41=11r$ and your answer is $5^r$.
Michael Burr
- 32,867
-
This is rather embarrassing but I still don't understand it. I do appreciate your help. Do you mind elaborating even further please? – patrickdahal Mar 06 '16 at 20:32
-
-
I understand that 5^40 ≡ 1 (mod41) but I don't quite get the part where you have said to find a k so that the exponent is a multiple of 11. I do apologise if this is something tedious – patrickdahal Mar 06 '16 at 20:46
-
So, you understand that $5^{40k+41}\equiv 5\mod 41$. We would like to find a $k$ so that $40k+41=11r$ because then $5^{40k+41}=5^{11r}=(5^r)^{11}$ and $5^r$ will be the answer that you're looking for. – Michael Burr Mar 06 '16 at 21:02
-
I get (-3) as the value of k and 11 as the value of r. Is that correct? – patrickdahal Mar 06 '16 at 22:01
-
There are many possible solutions, but $r=11$ does work (I used $k=2$ to get $r=11$). You don't have to ask if it's correct, you could compute $5^r$ to see if it has the correct properties. – Michael Burr Mar 06 '16 at 22:07