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 .
Sententia cdsmithus 
Here is my normal computation of the modular inverse in Scheme, using a method very similar to yours:
(define (inverse x m)
(let loop ((x (modulo x m)) (a 1))
(cond ((zero? x) #f) ((= x 1) a)
(else (let ((q (- (quotient m x))))
(loop (+ m (* q x)) (modulo (* q a) m)))))))
I discussed modular arithmetic, including the inverse, at http://programmingpraxis.com/2009/07/07/modular-arithmetic/.
Can you do it for finite fields?
Yes.
Indeed, this is often referred to as the Extended Euclidean Algorithm, or rather, it’s a simple application of it.
My wife informs me, that if your intentions was to say ‘The opinions of cdsmith’ then you need to put ‘cdsmith’ into the genitive case which is ‘cdsmithi’, so it should say ‘Sententia cdsmithi’.
Unless it’s third declension (often used for foreign, i.e. non-Latin) words, in which case it’d be “Sententia cdsmithis”
Actually, there’s about a 15 year long story around the blog name… far too involved and silly to tell here. So I understand it’s bad grammar, but that’s just how it is.
Also, the extended Euclidean (which I call “Egcd”) is usually done to give both the inverse of p in Z(q) and the inverse of q in Z(p) – at the same time! Here’s my work-up, taken from a utility module of mine:
eGCD a b = eGCDWorker a b (1,0) (0,1) where
eGCDWorker _ 0 (m1,n1) _ = (m1,n1)
eGCDWorker 0 _ _ (m2,n2) = (m2,n2)
eGCDWorker m n (m1,n1) (m2,n2) = eGCDWorker n r (m2,n2) (m3,n3) where
(q , r) = quotRem m n
(m3,n3) = (m1 – q*m2, n1 – q*n2)
When q is prime, the multiplicative group is cyclic, meaning that one can find a generator x such that all nonzero elements are of the form x^i for some i. For extensive computations in a fixed field, it pays to store two tables i -> x^i and i -> x^i + 1, and carry out all computations in terms of the representation i. Versions of the computer algebra system GAP used this approach, for example.
When q is not prime, this idea is less useful. x^i +1 is less frequently a unit, for example. It makes a good exercise in first year algebra to decide nevertheless the structure of the group of multiplicative units.
what is the multiplicative inverse of negative 3 and 2