How to compute ElGamal decryption by hand Lets say that $u=3, x=5, v=2$, how do we work out $u^{-x}*v$, so $3^{-5} * 2$. I know how to work out the answer if it was $3^5 * 2$ but how do we do it with negative exponents?
We're not trying to compute $3^{-5}\ast 2$, but instead we're trying to compute $3^{-5}\ast 2\mod p$ for some prime $p$.
This is notation for $(3^{-1})^5\ast 2\mod p$, so if we can compute what $3^{-1}\mod p$ is, you can just plug that value in and do computations like you'd expect.
Note that $3^{-1}\mod p$ means the element $u\in(\mathbb{Z}/p\mathbb{Z})^\times$ such that $u\ast 3\equiv 1\mod p$.
For example, because $2\ast 2\mod 3 \equiv 1\mod 3$, we have that $2^{-1} \mod 3= 2$.
Or, because $2\ast 3\equiv 1\mod 5$, we have that $2^{-1}\mod 5\equiv 3$.
The quantity $u^{-1}$ ends up being uniquely defined (when it exists --- $2\ast 3\equiv 0\mod 6$ means that $2^{-1}\mod 6$ can't exist), but note that it depends on both $u$ and $p$.

A computationally inefficient (but conceptually simple) way to compute $3^{-1}$ is via Fermat's Little Theorem, which states that:


  If $a\in\mathbb{Z}$, then $a^p\equiv a\mod p$


If $a\neq 0$, this is equivalent to $a^{p-1}\equiv 1\mod p$, and therefore $a^{p-2}\equiv a^{-1}\mod p$.
So we can compute $3^{-1}\mod p\equiv 3^{p-2}\mod p$, which you can do by hand.
If $p$ is large this might be annoying, but there are some tricks to speed it up (known as exponentiation by squaring).

A more computationally efficient way to compute this quantity is the Extended Euclidean Algorithm. This requires more explanation though, and if you want to know more about it you can probably find some resources online explaining it (it's a standard topic in elementary number theory courses).