Calculating Multiplicative Inverses in Modular Arithmetic
I’m sure plenty of people already know this, but I ran into it today, and it’s interesting… so here it is. A common and very easy result in abstract algebra is that the ring (where is any positive integer) contains a multiplicative inverse for (with ), if and only if . But what if you want to know what the multiplicative inverse is? Well, for small values of , you could just try numbers until one of them works. It turns out that also has a multiplicative inverse (namely, ), so it must also be relatively prime to … that helps when we’re doing the math mentally, but less so with a computer, since every possibility still requires some amount of work.
It turns out there’s a slightly faster way to find multiplicative inverses in , and it ban be done by doing the calculation of by the Euclidean algorithm, and tracing our own calculation through the steps. For those who may not remember, the Euclidean algorithm for the greatest common divisor depends on the fact that the greatest common divisor of and is the same as the greatest common divisor of and the remainder when is divided by . So, for example: . In our case, we start with the assumption that , so ultimately, the process will end with .
That’s all the setup we need. Here are the two cases for our calculation:
Case 1: . Clearly, the muliplicative inverse of one is one, so we are done.
Case 2: . Here, we reduce the problem to the next step in the chain of the Euclidean algorithm. Restating the problem, we wish to find a such that , for any integer .
Using simple division, we know that we can write , where are integers and . But, and this is important, we also know that (the next step in the Euclidean algorithm), so we can actually refine our inequality to . Now, by solving a smaller instance of this same problem, we can find such that . Another way of putting this is that divides .
Now we are done. We simply choose . Then . By examining each term separately, it’s clear that this is evenly divisible by , so we have , and we’re done.
Here’s some code to compute this in Haskell:
inverse :: Integral a => a -> a -> a inverse q 1 = 1 inverse q p = (n * q + 1) `div` p where n = p - inverse p (q `mod` p)
And there you have it, multiplicative inverses in .