[Math] Find inverse of 15 modulo 88.

discrete mathematicsgcd-and-lcminverse

Here the question: Find an inverse $a$ for $15$ modulo $88$ so that $0 \le a \le 87$; that is, find an integer $a \in \{0, 1, …, 87\}$ so that $15a \equiv1$ (mod 88).

Here is my attempt to answer:

Find using the Euclidean Algorithm, we need to find $\gcd(88, 15)$, that must equal to $1$ to be possible to find an inverse of $15 \pmod{88}$.

\begin{align*}
88 & = 5 \times 15 + 13\\
15 & = 1 \times 13 + 2\\
13 & = 6 \times 2 + 1\\
2 & = 2 \times 1 + 0
\end{align*}

So,
$$\gcd(88, 15) = 1$$

Now, we need to write this into the form:
$$\gcd(88, 15) = 88x + 15y.$$

And find $x$ and $y$.

\begin{align*}
1 & = 13(1) + 2(-6)\\
& = 13(7) + 15(-6)\\
& = 88(7) + 15(-41)
\end{align*}

So, $x = 7$ and $y = -41$.

So, an inverse of $15 \pmod{88} = -41$. Now, I need to find an inverse that is between $0$ and $87$. What is a good easy approach to find other inverses? Any ideas please?

Best Answer

$x$ is an inverse of $15 \pmod{88}$ if and only if $x=88n-41$ for some (any) integer $n$, because it is necessary and sufficient that $15(-41+x)$ is divisible by $88$, but this is equivalent to $(-41+x)$ being divisible by $88$.