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

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!

• just not got anything to go by, not many examples anywhere of this type, I've tried but what do I look up to find them, any links? – Anonymous May 2 at 17:31
• thanks but thats not really what im after, I just want a straightforward step by step solution of a question similar to the one above to help my understanding preferably from different website thats got a few. Appreciate it anyway though! – Anonymous May 2 at 17:43

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.

• How did you compute $1/5$ and $34^{11}$ and $15^{11}?$ Those omitted steps seem to be where most of the work is this way. – Bill Dubuque May 3 at 3:54
• This is from straightforward calculation and it is possible in several ways by successive simplifications $34^2=28; \space 34^3=12; \space 34^9=12^3; \space 34^{11}=12^3\cdot15^2\ne5$ $15^2=37; \space 15^3=38; \space 15^4=6; \space 15^{11}=6^2\cdot15^3=36\cdot38=5$. – Piquito May 4 at 13:30
• Besides $5x=47y+1$ easily gives $x=19$ – Piquito May 4 at 13:31
• I think in the first line you used Fermat little theorem ..... correct? if so why are you sure that 47 does not divide x (as it is the first condition that must be satisfied for Fermat little theorem to be applied) – hopefully Jun 1 at 16:09
• Also I do not understand why in the first line of your answer $x^23 \equiv 1$ (I can see you are using equality sign instead of $\equiv$ sign ..... correct?) – hopefully Jun 1 at 17:08

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

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

• It's not clear what you did. You should explain why you choose those particular powers so we can tell whether it is a general method or lucky coincidence that doesn't generalize. – Bill Dubuque May 2 at 20:06
• 3 rounds of Fermat chose the powers via the exponent rules and being the least power over 46. and yes I know $-(6^6)\bmod 47$ also can work. – Roddy MacPhee May 2 at 20:09
• okay one gives -5 the other 5 because 11 is odd. – Roddy MacPhee May 2 at 20:25
• It seems like pure luck. Essentially you are using that $\,11k \equiv 2\pmod{\!46}$ for $\,k = 5\cdot 6\cdot 6\,$ so raising $\,x^{11}\equiv 5\pmod{\!47}$ to power $k$ yields $\, x^2\equiv 5^k.\,$ You got lucky that your computation of $5^k$ yielded on obvious perfect square. That won't work in general. In fact $\,k\equiv 42\pmod{\!46}$ so you compute $\,5^{42},\,$ which is the square of what I did. Nor do you explain how you chose the correct square root (which you originally had wrong). Without any explanation it is magic - not math. – Bill Dubuque May 2 at 20:49
• that last part was checked later. all I did was $11\cdot5=55\equiv 9 \bmod 46$ as long as I didn't hit an exponent that was a factor of 46, I knew the next exponent would drop. this tends to bring the exponent down to 2 then you can sqrt it. and figure out which sqrt is required. – Roddy MacPhee May 2 at 20:54