Skip to content

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 $\mathbb{Z}_q = \mathbb{Z}/q\mathbb{Z}$ (where $q$ is any positive integer) contains a multiplicative inverse for $p$ (with $0 < p < q$), if and only if $\gcd(p,q) = 1$.  But what if you want to know what the multiplicative inverse is?  Well, for small values of $q$, you could just try numbers until one of them works.  It turns out that $p^{-1}$ also has a multiplicative inverse (namely, $p$), so it must also be relatively prime to $q$… 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 $\mathbb{Z}_q$, and it ban be done by doing the calculation of $\gcd(p,q)$ 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 $q$ and $p$ is the same as the greatest common divisor of $p$ and the remainder when $q$ is divided by $p$.  So, for example: $\gcd(12,8) = \gcd(8, 4) = \gcd(4, 0) = 4$.  In our case, we start with the assumption that $\gcd(q,p) = 1$, so ultimately, the process will end with $\ldots = \gcd(?, 1) = \gcd(1,0) = 1$.

That’s all the setup we need.  Here are the two cases for our calculation:

Case 1: $p = 1$.  Clearly, the muliplicative inverse of one is one, so we are done.

Case 2: $p > 1$.  Here, we reduce the problem to the next step in the chain of the Euclidean algorithm.  Restating the problem, we wish to find a $p'$ such that $pp' = nq + 1$, for any integer $n$.

Using simple division, we know that we can write $q = mp + r$, where $m,r$ are integers and $0 \leq r < p$.  But, and this is important, we also know that $\gcd(q,p) = \gcd(p,r)$ (the next step in the Euclidean algorithm), so we can actually refine our inequality to $0 < r < p$.  Now, by solving a smaller instance of this same problem, we can find $r'$ such that $rr' \equiv 1 \mod p$.  Another way of putting this is that $p$ divides $rr' - 1$.

Now we are done.  We simply choose $n = p - r'$.  Then $nq + 1 = (p - r')(mp + r) + 1 = (mp + r - mr')p - (rr' - 1)$.  By examining each term separately, it’s clear that this is evenly divisible by $p$, so we have $p' = (nq + 1) / p$, 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 $\mathbb{Z}_q$.

Advertisements

11 Comments

Leave a Comment
1. programmingpraxis / Jul 21 2009 6:59 am

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

2. Aaron / Jul 21 2009 2:56 pm

Can you do it for finite fields?

• lpsmith / Jul 21 2009 3:24 pm

Yes.

3. lpsmith / Jul 21 2009 3:22 pm

Indeed, this is often referred to as the Extended Euclidean Algorithm, or rather, it’s a simple application of it.

4. Joe / Jul 21 2009 6:36 pm

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

• BMeph / Jul 21 2009 6:52 pm

Unless it’s third declension (often used for foreign, i.e. non-Latin) words, in which case it’d be “Sententia cdsmithis”

• cdsmith / Jul 23 2009 9:18 am

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.

5. BMeph / Jul 21 2009 6:41 pm

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)

6. Dave / Jul 22 2009 8:26 am

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.

7. Renaya / Mar 1 2012 8:57 am

what is the multiplicative inverse of negative 3 and 2