How to calculate $(k^x)^{-1} \pmod m$ I'm trying to follow this example of ElGamal's encryption scheme (page 2, slides 3 & 4), but don't understand this step (decryption, step 2):
$$(k^x)^{-1} \pmod m$$
Where
$$k = 10,\ x = 9,\ m = 13$$
The slide shows that it becomes $$12^{-1} \pmod{13}= 12$$
Where did 12 come from? Also, can you help me see how the above equals 12?
I calculate:$$12^{-1} = \frac{1}{12}$$
 A: Mod $13\!:\ 10\equiv -3\:$ so $\rm\: 10^9 \equiv ((-3)^3)^3\equiv (-27)^3\equiv (-1)^3\equiv -1,\:$ and $\rm\:(-1)^{-1}\equiv -1\equiv 12$
As above, generally modular arithmetic is easier using the least residue reps $\:0,\pm1,\pm2,\ldots, \pm6\:$ versus $\:0,1,2,\ldots 12\:$ modulo $13$.
A: Over the rationals, $\mathbb{Q},$ we have
$$ 12^{-1} = \frac{1}{12}$$
but over the integers modulo $13,$ $\mathbb{Z}_{13},$ we have
$$ 12^{-1} \equiv x \pmod{13}$$
were $x$ is the multiplicative inverse of $12$ modulo $13.$
To find $x,$ follow this argument. Since $$12^{-1} \equiv x \pmod{13},$$ we have $$12a \equiv 1 \pmod{13}.$$ Recall $1 \pmod{13} = 1 + 13k$ for some integer $k.$ So
$ 12x = 1 + 13k .$ Rearrange,
$$ 12x - 13k = 1.$$
This is similar to what the extended Euclidean algorithm gives us:
$$ 12x + 13k = \gcd(12, 13).$$
So compute the extended Euclidean algorithm on $12, 13$ you will get $12$ as the inverse (here is one nice online calculator and another one; both perform extended GCD).

Another method is to construct the multiplication table module $13$ and look for an entry $x$ such that $$ 12x \equiv 1 \pmod{13}$$
