Calculating $x^{103} \equiv 2 \pmod{143}$

Question

I need to find x, given that: $0\leq x \leq 143$ and $x^{103}\equiv 2 \pmod{143}$. I tried to use Euler's theorem $p(143)=120$, but it didn't help.

Answer 1

Consider

$$x^{103}\equiv2 \pmod {13}$$ $$x^{103}\equiv2 \pmod {11}$$

en

$$x^7\equiv2 \pmod {13}$$ $$x^3\equiv2 \pmod {11}$$

$7$ is the common primitive root $\bmod {13}$ and $\bmod {11}$

$7^{11}\equiv2 \pmod {13}$, $7^3\equiv2 \pmod {11}$, and

if $(7^t)^7\equiv2 \pmod {13}$, $7t\equiv 11 \pmod {12}$, then $t=5\pmod {12}$

if $(7^s)^3\equiv2 \pmod {13}$, $3s\equiv 3 \pmod {10}$, then $s=1\pmod {10}$

so, the root $x$ is decided by

$$x\equiv 7^5\equiv 11 \pmod {13}$$ $$x\equiv7 \pmod {11}$$

then

$$x\equiv128 \pmod {143}$$

Answer 2

We can solve each of the following separately and find the common solutions:

$x^{103} \equiv 2 \pmod{11}$

$x^{103} \equiv 2 \pmod{13}$

They simplify by Fermat's little theorem to:

$x^3 \equiv 2 \pmod{11}$

$x^7 \equiv 2 \pmod{13}$

It is now easy to check all small cases to get the solutions:

$x \equiv 7 \pmod{11}$

$x \equiv 11 \pmod{13}$

When solved these give:

$x \equiv 128 \pmod{143}$

Answer 3

If you want to, you can use Euler to say (mod $143$) that $x^{120}\equiv 1$ so that $x^{-17} \equiv 2$

Now note that $103=6\times 17 +1$ so that $$2\equiv x^{103}\equiv (x^{17})^6x$$ whence , on dividing by $(x^{17})^6$, and using $x^{-17}\equiv 2$ $$x\equiv 2\times (x^{-17})^6\equiv 2^7\equiv 128$$