Question

Find an inverse of 16 modulo 17. That is solve 16x=1(mod 17)

Answer 1

-1 is the inverse of 16 modulo 17.

Explanation:

To find : An inverse of 16 modulo 17 i.e.
`16x=1(mod 17)`?

Solution :

First we find the GCD of (17,16) using Euclid's algorithm,

`17=16* 1+1`

Remainder is 1.

Which means, GCD(17,16)=1

Using back substitution we get,

`1=17-16(1)`

`\Rightarrow 16(-1)=1+17(-1)`

`\Rightarrow 16(-1)=1(\mod 17)`

i.e. -1 is the inverse of 16 modulo 17.

On comparing with
`16x=1(mod 17)`

The value of x=-1.