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

Question

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.

Answer 1

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

Answer 2

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