How to solve $108 = m^{37} \pmod {143}$

Question

I've tried this in Wolfram Alpha and got the value for $m$ that I expected, however I would like to know how to solve it rather than just the answer.

Answer 1

Note that $37$ is coprime to $\phi(143)(=\phi(11\times13)=120$). So in the multiplicative group of order 120, consisting integers coprime to $143,\ x\mapsto x^{37}$ is an automorphism of groups (suffices to know it is a bijection).

Its inverse is the map $x\mapsto x^a$ with $a$ being the inverse of 37 mod 120. (It happens that $a=13$ here.)

So, for $x$ coprime to 143, we can factorize the identity map ( Euler's theorem states $x^{120}$ is 1 mod 143) $x\mapsto x ^1 = ({x^{13}})^{37}\pmod {143}$

Applying for your case $x=108$, we get $m=108^{13}\pmod{143}= 69\pmod{143}$.

Answer 2

We work in the ring $R=\Bbb Z/143$. Its units form a group $R^\times$ with $\phi(143)=143\cdot\left(1-\frac 1{11}\right)\left(1-\frac 1{13}\right)=120$ elements. We want to solve in this group $$ 108=m^{37}\ . $$ We start from this, take the $13$.th power and get $$ m=m^{481}=(m^{37})^{13}=108^{13}=69 $$ in $R$. (We had to get the inverse of $37$ modulo $120$, it is $13$.) One checks that this is a solution, to have the converse too.

---

sage search for the solution:

sage: R = Zmod(143)
sage: for m in R:
....:     if m^37 == R(108):
....:         print m
....:         
69
sage: R(108)^13
69

Answer 3

By Euler's theorem, $x^{\varphi (143)}\cong1\pmod{143}$, if $x$ and $143$ are coprime.

$\varphi (143)=\varphi (13)\cdot \varphi (11)=(13-1)(11-1)=(12)(10)=120$.

Next, $(13)(37)-4(120)=1$. That is, $(13)(37)\cong1\pmod{120}$. (This can be done with the Euclidean algorithm, since $37$ and $120$ are coprime.)

Now ${(x^{37})}^{13}=x^{481}={(x^{120})}^{4}\cdot x\cong x\pmod{143}\implies 108^{13}\cong x\pmod{143}\implies x=69$. (For the last step I used Wolfram alpha.)

Answer 4

As $\lambda(143)=60,$ let us find integer $a,b$ such that $$37a+60b=1$$

Like my answer here in Solving a Linear Congruence, $$37\cdot13-60\cdot8=1$$

$$m=m^{37\cdot13-60\cdot8}\equiv(108)^{13}\cdot1^{-8}\pmod{143}$$

$108\equiv-2\pmod{11}\implies(108)^{13}\equiv(-2)^{13}\equiv(-2)^3\equiv3\ \ \ \ \ (1)$ using Fermat's Little Theorem

Similarly, $(108)^{13}\equiv4\pmod{13}\ \ \ \ \ (2)$

Apply Chinese Remainder Theorem, on $(1),(2)$