# How to solve the congruence equation $x^e\equiv c \pmod p$ for $x$

Given the equation:

$$x^e\equiv c \pmod p$$

where $p$ is prime number, $c$ is positive integer and $e$ is positive integer and $\gcd(e, p-1) = 1$. Explain how would you solve given equation.

Also, using that explanation solve next equation:

$$x^{77} \equiv 2 \pmod{246}$$

I know that I need to use Chinese reminders theorem but I am not sure how... Please can you provide some explanation how to solve this.

• 246 is not prime. You can use the chinese remainder theorem to split it into prime factors before you can apply the answer given by Watson, but I think his answer may work if there exists a solution anyways. Commented Sep 1, 2016 at 20:16

By Bézout's theorem, there are integers $a,b$ such that $ae+b(p-1)=1$. Therefore, $$x = x^{ae+b(p-1)}\;\; \equiv c^a \cdot (x^{p-1})^b \equiv c^a \pmod p.$$

For your specific question, you have $$\begin{cases} x^{77} \equiv x \equiv 2 \equiv 0 \pmod 2\\ x^{77} \equiv x \equiv 2 \pmod 3\\ x^{77} \equiv 2 \pmod{41}\\ \end{cases}$$ The last equation becomes, because of the Bézout's identity $-25 \cdot 40 + 13 \cdot 77 = 1$, $$x \equiv 2^{13} \equiv 33 \pmod{41}$$ Then using the CRT you get $x \equiv 74 \pmod{246}$.

• In fact the computations which you omitted (inverse computation, and CRT lifting) can be done completely with simple mental arithmetic if you know the shortcuts - see my answer. Commented Sep 1, 2016 at 23:20
• If I understood, there are three equations mod 2, 3 and 41. You have transformed only the last one, and used CRT for which equations? Commented Sep 4, 2016 at 11:40
• @clzola: Yes. I only needed to transform the last one because for the first one I used $y^{77} \equiv 0 \pmod 2 \implies y \equiv 0$, and for the second one $y^2 \equiv 1 \pmod 3$ if $y≠0$. $\tag*{}$ I have the system $$\begin{cases} x \equiv 0 \pmod 2\\ x \equiv 2 \pmod 3\\ x \equiv 33 \pmod{41}\\ \end{cases}$$ so I used the CRT to solve it. Commented Sep 4, 2016 at 11:50
• @clzola: When you have $am+bn=1$, with $m,n$ coprime, then the system $$\begin{cases} x \equiv r \pmod n\\ x \equiv s \pmod m\\ \end{cases},$$ has the solution $x \equiv r(1-bn) + s(1-am) \pmod{nm}$. Commented Sep 4, 2016 at 11:53
• @Watson, thank you! Does this equation has some name, so I can look on google for more examples. I have only this one, but would be great if I could find more... Commented Sep 4, 2016 at 11:59

Yes, CRT works. $\$ Easily $\,x\equiv 2\pmod{6}\,$ and $\ x\!\pmod{41}\,$ can be computed mentally:

${\rm mod}\ 40\!:\,\ \color{#c00}{\dfrac{1}{77}}\equiv \dfrac{-39}{-3}\equiv \color{#c00}{13},\$ so $\,\ {\rm mod}\ \color{#0a0}{41\!:\ \, x}\equiv 2^{\color{#c00}{\large 1/77}}\!\equiv 2^{\color{#c00}{\large 13}}\!\equiv 2^{\large 3}(2^{\large 5})^{\large 2}\equiv 8(-9)^{\large 2}\equiv \color{#0a0}{-8}$

${\rm mod}\ 6\!:\ 2\equiv x\equiv \color{#0a0}{-8+41k}\equiv -8\!-\!k\!\iff\! k\equiv 2,\,$ so $\,x\equiv -8+41\cdot 2\equiv 74\pmod{\!6\cdot 41}$