How to solve $x=2^{-18}$ (mod 143)

Question

I have to solve the following equation: $x=2^{-18} \mod 143$.

The problem is that I can't use Fermat's little theorem as $\varphi(143)=120$ which doesn't help at all. The other method I know is to find the inverse of $2^{18} \mod 143$ using Euclid's extended algorithm but that would mean to find the inverse of $362144 \mod 143$ which doesn't seem like a good method to me...Any other ideas how I can solve this? Thank you!

Answer 1

You can work modulo $11$ and $13$ and stitch the results together using the Chinese Remainder Theorem. For example:

$$2^{18}\cdot 2^2=(2^{10})^2\equiv 1 \bmod 11$$ by Fermat, so that $2^{-18}\equiv 4 \bmod 11$ as a start.

For CRT note that $6\cdot 11-5\cdot 13=1$ so that $-65a+66b=c \equiv a \bmod 11, \equiv b \bmod 13 $, and the same is true of $c$ reduced modulo $143$.

Answer 2

Here are two approaches. First by exponentiation and Gauss's algorithm, second by CRT.

${\rm mod}\ 143\!:\,\ \color{#c00}{2^{18}}\equiv (2^2\!\cdot\!\!\overbrace{ 2^7}^{\large -15}\!)^2\equiv 60^2\equiv 20\overbrace{(37)}^{\large 3(60)}\equiv 5\!\overbrace{\!(5)}^{\large 4(37)}\!\!\equiv \color{#c00}{25}$

Therefore $\,\ \color{#c00}{2^{-18}\equiv \dfrac{1}{25}}\equiv \dfrac{6}{150}\equiv \dfrac{6}7\equiv \dfrac{120}{140}\equiv \dfrac{120}{-3}\equiv -40\ $ by Gauss's Algorithm

---

Or, we can use little Fermat and CRT (Chinese Remainder) and, again, all mental arithmetic.

${\rm mod}\ 11\!:\,\ 2^{10}\equiv 1\,\Rightarrow\, 2^{-18}\equiv (2^{10})^2 2^{-18}\equiv 2^2\equiv 4$

${\rm mod}\ 13\!:\,\ 2^{12}\equiv 1\,\Rightarrow\, 2^{-18}\equiv (2^{12})^2 2^{-18}\equiv 2^6\equiv -1$

${\rm mod}\ 11\!:\,\ 4\equiv x\equiv -1+13 \color{#a0f}k\equiv -1+2k\iff 2k\equiv 5\equiv 16\iff \color{#a0f}{k\equiv 8}$

Substituting: $\,\ x\equiv -1+13( \color{#a0f}{8\!+\!11n})\equiv 103+143n$

Answer 3

Finding the inverse is made a bit easier using this method: $$2^2 \equiv 4\bmod 143$$ $$2^4 \equiv 4^2 \equiv 16 \bmod 143$$ $$2^8 \equiv 16^2 \equiv 256 \equiv 113 \bmod 143$$ (it's getting tricky here) $$2^{16} \equiv 113^2 \equiv 12769 \equiv 42 \bmod 143$$ $$2^{18} \equiv 2^{16}2^2 \equiv 42*4\equiv168\equiv25 \bmod 143$$ And since 25 and 143 are coprime, by Euclid's algorithm we have: $$ \begin{matrix} - & - & 5 &1&2&1&1\\ 0 & 1 & -5 & 6 & -17 & 23 & -40 \\ 143 & 25 & 18 & 7 & 4 & 3 & 1 \\ \end{matrix} $$ So -40 is the inverse of $2^{18}\bmod143$, thus $x \equiv 103\bmod143$. Takes some more time than other solutions, but it requires only Euclid's extended algorithm and some long division to do 12369 mod 143.