Question

 Define the multiplicative inverse in modular arithmetic and identify the multiplicative inverse of 6 mod 13 while explaining the algorithm used.

Answer 1

The multiplicative inverse of a number x modulo m is a number y such that

$xy \equiv 1 \pmod m$

and we write $y \equiv x^{-1}$

The algorithm used for finding the inverse is known as Euclid's algorithm - it's a means of deducing the GCD of two given integers. In this case, we want to find x such that

$6x \equiv 1 \pmod{13}$

We have

$13 = 12 + 1 = 2•6 + 1$

(the remainder term here is the GCD)

Now,

$1 = 13- 2•6$

and taken mod 13, we have

$1 \equiv 13 - 2\cdot6 \equiv -2 \cdot 6 \pmod{13}$

$and \\ -2 \equiv 11 \pmod{13}$

so the inverse of 6 mod 13 is 11. Indeed,

$11\cdot6 \equiv 66 \equiv 65 + 1 \equiv 5\cdot13+1 \equiv 1\pmod{13}$