The multiplicative inverse of a number x modulo m is a number y such that
[tex]xy \equiv 1 \pmod m[/tex]
and we write [tex]y \equiv x^{-1}[/tex].
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
[tex]6x \equiv 1 \pmod{13}[/tex]
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
[tex]1 \equiv 13 - 2\cdot6 \equiv -2 \cdot 6 \pmod{13}[/tex]
and
[tex]-2 \equiv 11 \pmod{13}[/tex]
so the inverse of 6 mod 13 is 11. Indeed,
[tex]11\cdot6 \equiv 66 \equiv 65 + 1 \equiv 5\cdot13+1 \equiv 1\pmod{13}[/tex]
