(Exercise 3.9 from the course notes)

Find the inverse of 37 modulo 53

Proposition 11 (Inverse of a product).

Proposition 12 (Proper inverse).
Sometimes, trial and error is enough, but here we proceed with certainty. We start by performing the Euclidean algorithm

\[
\begin{aligned}
& 53=37+16 \\
& 37=16 * 2+5 \\
& 16=5 * 3+1
\end{aligned}
\]

From this, we deduce a Bézout's identity

\[
\begin{array}{r}
16-5 * 3=1 \\
16-(37-16 * 2) * 3=1 \\
53-37-(37-(53-37) * 2) * 3=1 \\
7 * 53-10 * 37=1
\end{array}
\]

We look modulo 53: 10 is the inverse of 37 modulo 53.