Congruence equations in the form $x^k \equiv b \bmod m$

Question

In my textbook its described as finding $k\;$th roots moduluo $m$. How do you solve equations of this form as I can't find any examples anywhere? I am just looking for a step by step example so I can understand how to solve them. An example question could be: solve $x^{11} \equiv 5 \bmod 47$.

Any links to any websites or videos explaining the congruence equations in this form would be greatly appreciated also. Thanks!

Answer 1

Hint $\bmod 47\!:\,\ x^{\large 11}\equiv 5\,\overset{(\ \ )^{\Large 21}}{\Longrightarrow} x\equiv 5^{\large 21}\ $ by $\,11\cdot 21\equiv 1 \pmod{\!46}\,$ and little Fermat.

Thus $\,x\equiv \dfrac{\color{#c00}{5^{\large 23}}}{5^{\large 2}}\equiv \dfrac{\color{#c00}{\bf -1}}{25}\equiv \dfrac{-2}{50}\equiv\dfrac{45}3\equiv 15,\,$ by $\, \color{#c00}{5^{\large 23}} \equiv \left(\dfrac{5}{47}\right) = \left(\dfrac{47}{5}\right)=\left(\dfrac{2}{5}\right)= \color{#c00}{\bf -1}\,$

---

Or $\ x^{\large 23}\equiv -1\ $ by $\ (x^{\large 23})^{\large 11} = (x^{\large 11})^{\large 23} \equiv \color{#c00}{5^{\large 23} \equiv\bf -1}\, $ so $\ x\equiv \dfrac{x^{\large 23}}{(x^{\large 11})^{\large 2}}\equiv \dfrac{-1}{25}\equiv 15\,$ as above.

---

The first method raised $\,x^{\large 11}\equiv 5\,$ to power $\, \dfrac{1}{11}\equiv 21\pmod{\!46}\,$ to get the $11$'th root, using

$\!\bmod 46\!:\,\ \dfrac{1}{11}\equiv \dfrac{5}{55}\equiv \dfrac{5}9\equiv \dfrac{25}{45}\equiv \dfrac{25}{-1}\equiv 21,\, $ computed by Gauss's algorithm, as above.

In the second method instead of using $\,x^{\large 46}\equiv 1\,$ we use $\,x^{\large 23}\equiv -1.\,$ Here $\,1/11\,$ is simpler

$\!\bmod 23\!:\,\ \dfrac{1}{11}\equiv \dfrac{2}{22}\equiv \dfrac{2}{-1}\equiv -2\ $ so $\ 5\equiv x^{\large 11}\,\overset{\large(\ \ )^{\Large -2}\!}\Longrightarrow\, 5^{\large -2}\equiv x^{\large-22}\equiv \dfrac{x}{x^{\large 23}}\equiv -x$

See this theorem for the general result when the power is coprime to the order(s).

Answer 2

Hint at another related way to think about it:

• $(x^{11})^5\equiv x^9\equiv 5^5\equiv 23 \bmod 47$ Because of $(a^b)^c=a^{bc}$, $a^{p-1}\equiv 1\bmod p$ for prime p, a not a multiple, and $55\equiv 9\bmod 46$ which is valid by extension of the above rules plus $1^n=1$ and the fact that the first multiple of a number greater than a non multiple is of lower remainder if 0 is considered highest. oh and 1 times anything is itself.
• $(x^9)^6\equiv x^8\equiv 23^6\equiv 6^2\bmod 47$ Because $54\equiv 8\bmod 46$
• $(x^8)^6\equiv x^2\equiv 6^{12} \bmod 47$ Because $48\equiv 2\bmod 46$
• $x\equiv -(6^6) \bmod 47$ Because $(-1)^{2n+1}=-1$, $6^6=992(47)+32$,$32^{11}=766570149339658(47)+42$ which is $-5\bmod 47$, but that means the other is $5\equiv 47$

three round of Fermat. two possible cases, but only one stated works because 11 is odd. EDIT : and here's a case that's not true:

$$4^3\equiv 5 \bmod 48$$

It's not true because:

$$y\equiv b\bmod m\implies y=mx+b$$

if y and m share a factor, then: $$y-mx=b$$ shows us, b will have that factor as well, by the inverse of the distributive property ( factoring out).

Answer 3

In $\mathbb F_{47}$one has $x^{46}=1$ then $x^{23}=\pm1$

► $x^{23}=1\iff x^{11}\cdot x^{12}=1\iff 5\cdot x^{12}=1\Rightarrow x^{12}=\dfrac 15=19$.

Then $\begin{cases}x^{12}=19\\x^{11}=5\end{cases}\Rightarrow x=\dfrac{19}{5}=19\cdot19=34$ and $34^{11}=21$ thus $x=34$ is not solution.

►$x^{23}=-1\iff x^{11}\cdot x^{12}=-1\iff 5\cdot x^{12}=-1\Rightarrow x^{12}=\dfrac {-1}{5}=28$.

Then $\begin{cases}x^{12}=28\\x^{11}=5\end{cases}\Rightarrow x=\dfrac{28}{5}=28\cdot19=15$ and $\boxed{15^{11}=5}$

Thus $\color{red}{x=15}$ is the only solution.