Question

By inspection (as discussed prior to Example1), find an inverse of 2 modulo 17 .

Short answer

Inverse of 2 modulo 17 is 9 .

Step-by-step solution

Step 1

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

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

First perform the Euclidean algorithm to determine $\gcd \left(\mathrm{a},\mathrm{m}\right)$:

$$\begin{gathered} 17=8·2+1 \\ 2=2·1+0 \end{gathered}$$

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

Step 2

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

$$\begin{gathered} \gcd \left(\mathrm{a},\mathrm{m}\right)=1 \\ =17-8·2 \\ =1·17-8.2 \end{gathered}$$

The inverse is then the coefficient of $a=2$which is -8 .

Since -8 mod 17 = 9, 9 is the inverse of a modulo m .