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

So far we have: \begin{align*} 7 &= 25 - 1\times18\\ &\equiv -1\times18 \pmod{25} \end{align*} We can substitute this into the equation for $4$: \begin{align*} 4 &= 18 - 2\times7\\ &\equiv 18 - 2\times(-1\times18) \pmod{25}\\ &\equiv 18 + 2\times18 \pmod{25}\\ &\equiv 3\times18 \pmod{25} \end{align*} \begin{align*} 3 &= 7 - 1\times4\\ &\equiv (-1\times18) - 1\times(3\times18) \pmod{25}\\ &\equiv -4\times18 \pmod{25} \end{align*} \begin{align*} 1 &= 4 - 1\times3\\ &\equiv (3\times18) - 1\times(-4\times18) \pmod{25}\\ &\equiv 7\times18 \pmod{25} \end{align*} Or slightly rearranged: \[18\times7 \equiv 1 \pmod{25}.\] This tells us that $x=7$ (or $x=32,57,\ldots$) will solve the equation $18x \equiv 1 \pmod{25}$.