Calculate the inverse of 36 modulo 101.

Theorem 2 (Chinese Remainder Theorem (CRT)).

Let $m_{1}, m_{2} \in$ be two coprime integers. Let $r_{1}, r_{2} \in \mathbb{N}$. There exists a unique $r \in$ $\left\{0, \ldots, m_{1} m_{2}-1\right\}$ such that:

$$
x \equiv r_{1}\left[m_{1}\right] \text { and } x \equiv r_{2}\left[m_{2}\right] \Longleftrightarrow x \equiv r\left[m_{1} m_{2}\right]
$$

Proof. Let $s_{1}$ be the inverse of $m_{1}$ modulo $m_{2}$ and $s_{2}$ be the inverse of $m_{2}$ modulo $m_{1}$. To prove the existence, it suffices to take:

$$
x \equiv r_{2} s_{1} m_{1}+r_{1} s_{2} m_{2}\left[m_{1} m_{2}\right]
$$

Now let's prove the uniqueness: let $x_{1}, x_{2}$ satisfy $x_{1} \equiv x_{2}\left[m_{1}\right], x_{1} \equiv x_{2}\left[m_{2}\right]$. Therefore, $m_{1} \mid x_{1}-x_{2}$ and $m_{2} \mid x_{1}-x_{2}$, hence $m_{1} m_{2} \mid x_{1}-x_{2}$, and thus $x_{1} \equiv x_{2}\left[m_{1} m_{2}\right]$.
$$
\begin{aligned}
0 \cdot 36+1 \cdot 101 & =101 \\
1 \cdot 36+0 \cdot 101 & =36 \\
-2 \cdot 36+1 \cdot 101 & =29 \\
3 \cdot 36-1 \cdot 101 & =7 \\
-14 \cdot 36+5 \cdot 101 & =1
\end{aligned}
$$

The inverse of 36 modulo 101 is therefore $-14 \equiv 87[101]$.