Find the inverses of 2,3,...,16 modulo 17.

Question

I need to find the inverses of 2,3,...,16 modulo 17 and use to solve (a) 5x ≡ 9 (mod 17); (b) 11x ≡ 3 (mod 17).

I found the inverse of 5 modulo 17, to be 7 modulo 17 and know to solve by multiplying both sides of 5x ≡ 9 (mod 17) by 7, not sure how to pass this point.

Answer 1

To calculate them all in a batch, it's probably better to use factorisation:

$0 \times 17 + 1$ is just $1$ so it will yield nothing.

$1 \times 17 + 1 = 18$, which is $2 \times 9 = 3 \times 6$. Therefore $2^{-1} = 9$ and $3^{-1} = 6$.

$2 \times 17 + 1 = 35$, which is $5 \times 7$. Therefore $5^{-1} = 7$.

And so on.

Once you have $5^{-1} = 7$, then $5x \equiv 9 \pmod{17}$ implies $7 \times 5x \equiv 7 \times 9$, so $x \equiv 63 \equiv 12$.