Find inverse of 15 modulo 88.

Question

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?

Answer 1

$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$.

Answer 2

Per Arthur's comment, recall the congruence classes identify all elements a given amount apart (e.g., $-1\equiv87\pmod{88}$). Thus, just add $88$ to your inverse until it gives an element between $0$ and $87$.

Answer 3

For a systemetic way, you have to use the Extended Euclidean Algorithm: if you have a Bézout's relation: $$u\times 88+v\times 15=1$$ the you know the inverse of $15$ is $v\bmod88$.

The following shows how to display the computation, taking into account that, in Euclid's algorithm, the remainder at each step is a linear combination of $88$ and $15$:

\begin{array}[t]{lrrrr} \text{Successive Divisions}& r_i & u_i & v_i & q_i\\ \hline & 88 & 1 & 0 & \\ 88 = {\color{red}5} \times 15 +\color{blue}{13} & 15 &0 & 1 & \color{red}5 \\ 15 = {\color{red}1} \times 13 + \color{blue}{2} & \color{blue}{13} & 1 & -5 & \color{red}1 \\ 13 = {\color{red}6} \times 2 + \color{blue}{1} & \color{blue}{2} & -1 & 6 & \color{red}6 \\ & \color{blue}{1} & 7 & -41\\[2ex] \hline \end{array} Thus the inverse of $15$ modulo $88$ is $\;-41\equiv 47\mod 88$.

Answer 4

    work             Translation(unnecessary once you know how to do this.)
    | 88    1    0   88 = 1(88) +  0(15)
 -6 | 15    0    1   15 = 0(88) +  1(15), add -6 x this row to the above row
  7 | -2    1   -6   -2 = 1(88) -  6(15), add  7 x this row to the above row
    |  1    7  -41    1 = 7(88) - 41(15)

Hence -41(15) ≡ 1 (mod 88)

Answer 5

$15n=88k+1$. But $15n$ ends either in $0$ or in $5$. So we are looking for a multiple of $88$ which ends either in $9$ or in $4$. The former case is impossible, since $88$ is an even number. Now, what is the first multiple of $8$ to end in a $4$ ? So $k_0=3$ is our first suspect. Unfortunately, in this case, $n_0\not\in\mathbb N$. So let's check $k_1=3+5=8$, since the cycle of $8x\bmod10$ has legth $5$. Bingo ! We have $n_1=47$.