Question 7.9.11

Suppose we want to solve the equation \[18x \equiv 1 \pmod{25}\] for integer $x$, and we don’t want to use brute force. (Solving this equation is equivalent to finding the inverse of $18$ mod $25$.) The Euclidean algorithm for finding the gcd of $25$ and $18$ might give us a clue. I’m going to write it in a slightly non-standard way:

\begin{align*} 25 - 1\times18 &= 7\\ 18 - 2\times7 &= 4\\ 7 - 1\times4 &= 3\\ 4 - 1\times3 &= 1 \end{align*} This tells us that the gcd is $1$, but maybe it can also help us solve the original equation. The first line tells us that $7\equiv -1\times18 \pmod{25}$. We want to find a similar equation for $1$, as that would solve our problem. Express the other remainders ($4$, $3$, and $1$) as $s\times18 \pmod{25}$ for some integer $s$, and hence solve the original equation for $x$. Show hint

Show answer