Question

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

(a) a=2, m=17

(b) a=34, m=89

(c) a=144, m=233

(d) a=200, m=1001

Short answer

1. 9
2. 55
3. 89
4. 996

Step-by-step solution

Step 1

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

$$\begin{gathered} a=2 \\ m=17 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 17=8.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

role="math" localid="1668582766676" $$\begin{gathered} \gcd (a,m)=1 \\ \gcd (a,m)=17-8.2 \\ \gcd (a,m)=1.17-8.2 \end{gathered}$$

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

Since role="math" localid="1668581974538" $-8\mathrm{mod}17=9\mathrm{mod}17,9$is also the inverse of a modulo m.

Step 2

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

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

First perform the Euclidean algorithm:

$$\begin{gathered} 89=2.34+21 \\ 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} \gcd (a,m)=1 \\ =3-1.2 \\ =1.3-1.2 \\ =1.3-1.(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.(89-2.34)-8.34 \\ =13.89-34.34 \end{gathered}$$

The inverse is then the coefficient of a, which is role="math" localid="1668583285119" $=-34$

Since $-34\mathrm{mod}89=-34+89\mathrm{mod}89,55\mathrm{mod}89,55$is also the inverse of a modulo m.

Step 3

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

$$\begin{gathered} a=144 \\ m=233 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 233=1.44+89 \\ 144=1.89+55 \\ 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} \gcd (a,m)=1 \\ =3-1.2 \\ =1.3-1.2 \\ =1.3-1.(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\cdot (89-1.55) \\ =34.55-21.89 \\ =34.(144-1.89)-21.89 \\ =34.144-55.89 \\ =34.144-55\cdot (233-1.144) \\ =89.144-55.233 \end{gathered}$$

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

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=200 \\ m=1001 \end{gathered}$$

First perform the Euclidean algorithm:

$$\begin{gathered} 1001=5.200 \\ 200=200.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 \\ =1001-5.200 \\ =1.1001-5.200 \end{gathered}$$

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

Since $-5\mathrm{mod}1001=-5+1001\mathrm{mod}1001=996\mathrm{mod}1001,996$is also the inverse of a modulo m.