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?

  • $\begingroup$ I added some formatting to your post - Please ensure I did not change the meaning (I had to assume the precedence for u^-x * v was $u^{-x} * v$ and not $u^{-x * v}$) $\endgroup$ – Ella Rose Aug 24 '19 at 15:05

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

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.