How to calculate $(k^x)^{-1} \pmod m$

Question

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}$$

Answer 1

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}$$

Answer 2

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$.