Question

By inspection (as discussed prior to Example 1 ), find an inverse of 4 modulo 9 .

Short answer

Inverse of 4 modulo 9 is 7 .

Step-by-step solution

Step 1

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

role="math" localid="1668572878435" $$\begin{gathered} a=4 \\ m=9 \end{gathered}$$

$ab\equiv 1\left(\mathrm{mod}\mathrm{m}\right)$if m divides $ab-1$.

$9|4b-1$

Since $4\mathrm{b}-1=4·7-1=28-1=27=3·9,\mathrm{b}=7$is a possible integer solution.

Thus $b=7$is the inverse of 4 modulo 9.

Step 2

ALTERNATIVE SOLUTION

The inverse of is an integer b for which $ab\equiv 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(\mathrm{a},\mathrm{m}\right)=1$

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

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

The inverse is then coefficient of 4, which is $-2$.

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