Question

Find an inverse of modulo for each of these pairs of relatively prime integers using the method followed in Example 2.

(a) $a=4,m=9$

(b)$a=19,m=141$

(c)$a=55,m=89$

(d)$a=89,m=232$

Short answer

1. 7
2. 52
3. 34
4. 73

Step-by-step solution

Step 1

a) The inverse of a modulo m is an integer$b$ for which $ab=1\left(\mathrm{mod}\mathrm{m}\right)$

$$\begin{gathered} a=4 \\ m=9 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 9=2.4+1 \\ 4=4.1 \end{gathered}$$

The greatest common divisor is then the last non zero remainder:$\gcd \left(a,m\right)=1$

Next we write the greatest common divisor as a multiple of a and m

$$\begin{gathered} \gcd \left(a,m\right)=1 \\ \gcd \left(a,m\right)=9-2.4 \\ \gcd \left(a,m\right)=1.9-2.4 \end{gathered}$$

The inverse is then the coefficient of a, which is $-2$

Since $-2\mathrm{mod}9-7\mathrm{mod}9,7$ is also the inverse of a modulom.

Step 2

b) The inverse of a modulom is an integer$b$ for which $ab=1\left(\mathrm{mod}\mathrm{m}\right)$

$$\begin{gathered} a=19 \\ m=141 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 141=7.19+8 \\ 19=2.8+3 \\ 8=2.3+2 \\ 3=1.2+1 \\ 2=2.1 \end{gathered}$$

The greatest common divisor is then the last non zero remainder:$\gcd \left(a,m\right)=1$

Next we write the greatest common divisor as a multiple of a and m

$$\begin{gathered} \gcd (a,m)=1 \\ =3-1.2 \\ =1.3-1.2 \\ =1.3-1.(8-2.3) \\ =3.3-1.8 \\ =3.(19-2.8)-1.8 \\ =3.19-7.8 \\ =3.19-7.(141-7.19) \\ =52.19-7.141 \end{gathered}$$

The inverse is then the coefficient of a, which is 52

Step 3

c) The inverse of a modulo m is an integer$b$ for which $ab=1\left(\mathrm{mod}\mathrm{m}\right)$

$$\begin{gathered} a=55 \\ m=89 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 89=1.55+34 \\ 55=1.34+21 \\ 34=1.21+13 \\ 21=1.13+8 \\ 13=1.8+5 \\ 8=1.5+3 \\ 5=1.3+2 \\ 3=1.2+1 \\ 2=2.1 \end{gathered}$$

The greatest common divisor is then the last non zero remainder:$\gcd \left(a,m\right)=1$

Next we write the greatest common divisor as a multiple of a and m

$$\begin{gathered} 7\gcd (a,m)=1 \\ =3-1.2 \\ =1.3-1.2 \\ =1.3-1\cdot (5-1.3) \\ =2.3-1.5 \\ =2.(8-1.5)-1.5 \\ =2.8-3.5 \\ =2.8-.(13-1.8) \\ =5.8-3.13 \\ =5\cdot (21-1.13)-3.13 \\ =5.21-8.(34-1.21) \\ =13.21-8.34 \\ =13.(55-1.34)-8.34 \\ =13.55-21.34 \\ =13.55-21.(89-1.55) \\ =34.55-21.89 \end{gathered}$$

The inverse is then the coefficient of a, which is 34

Step 4

d) The inverse of a modulo m is an integer$b$ for which $ab=1\left(\mathrm{mod}\mathrm{m}\right)$

$$\begin{gathered} a=89 \\ m=232 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 232=2.89+54 \\ 89=1.54+35 \\ 54=1.35+19 \\ 19=1.16+3 \\ 16=5.3+1 \\ 3=3.1 \end{gathered}$$

The greatest common divisor is then the last non zero remainder:role="math" localid="1668579544243" $\gcd \left(a,m\right)=1$

Next we write the greatest common divisor as a multiple of aand m

$$\begin{gathered} \gcd (a,m)=1 \\ =16-5.3 \\ =1.16-5.3 \\ =1.16-5.(19-1.16) \\ =6.16-5.19 \\ =6.(35-1.19)-5.19 \\ =6.35-11.19 \\ =6.35-11(54-1.35) \\ =17.35-11.35 \\ =17.(89-1.54)-11.54 \\ =17.89-28.54 \\ =17.89-2(232-2.89) \\ =73.89-28.232 \end{gathered}$$

The inverse is then the coefficient of a, which is 73