How to solve $x=2^{-18}$ (mod 143) 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!
 A: 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$.
A: 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$
A: 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.
