3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Anonymous May 2 at 17:31
  • $\begingroup$ 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! $\endgroup$ – Anonymous May 2 at 17:43
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque May 3 at 3:54
  • 1
    $\begingroup$ 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$. $\endgroup$ – Piquito May 4 at 13:30
  • 1
    $\begingroup$ Besides $5x=47y+1$ easily gives $x=19$ $\endgroup$ – Piquito May 4 at 13:31
  • $\begingroup$ 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) $\endgroup$ – Secretly Jun 1 at 16:09
  • $\begingroup$ 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?) $\endgroup$ – Secretly Jun 1 at 17:08
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Bill Dubuque May 2 at 20:06
  • $\begingroup$ 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. $\endgroup$ – Roddy MacPhee May 2 at 20:09
  • $\begingroup$ okay one gives -5 the other 5 because 11 is odd. $\endgroup$ – Roddy MacPhee May 2 at 20:25
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque May 2 at 20:49
  • $\begingroup$ 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. $\endgroup$ – Roddy MacPhee May 2 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.