- Multiplicative Inverses
- Indirect Means of Finding Multiplicative Inverses
- Effect of Modular Reduction on c = ax + by
- The Extended Euclidean Algorithm for Finding The Multiplicative Inverse of x modulo y
- Examples
- An Alternative Way of Viewing the Extended Euclidean Algorithm

Recall that the
multiplicative inverse in a modulo *n* world is defined as being the
number, *a*^{-1}, such that

(a)(a^{-1})
1 (mod n)

Thus, for example, 3 and 7 are multiplicative inverses of each other in a mod 10 world while 5 and 11 are multiplicative inverses of each other in a mod 27 world.

For very small moduli, finding the multiplicative inverse of a number is not terribly difficult to do via exhaustive search since, by definition,

(a)(a^{-1})
= kn + 1

So it becomes a simple matter of writing this as

(a^{-1})
= (kn + 1)/a

and trying successive values of k until one is found that results in the right hand side being an integer. All that is then left is to reduce the resulting integer modulo n.

But as the modulus grows, this process quickly becomes unwieldy and
impractical. What is needed is a more systematic means of finding *a*^{-1}.

Consider the following equation

ax + by = c

In a modulo *x* world, this reduces to

by c (mod x)

while in a modulo *y* world it reduces to

ax c (mod y)

If *c* happens to be 1, then *a* is the modulo *y*
multiplicative inverse of *x* while *b* is the modulo *x*
multiplicative inverse of *y*. All that remains is to develop a means of
find appropriate values of *a* and *b* such that *c* is equal to
1.

For example, consider the following relation where *x* is 3 and *y*
is 10

(7)(3) + (-2)(10) = 1

From this, we can immediately see that 7 is the modulo 10 multiplicative inverse of 3. By the same token, this also says that -2 is the multiplicative inverse of 10 modulo 3. Is this true? First, keep in mind that what it really says is that -2 is congruent to the multiplicative inverse of any value that is congruent to 10 in a modulo 3 world. In a modulo 3 world, 10 is congruent to 1 and so is -1, hence we have the result that 1 is the multiplicative inverse of 1 in a modulo 3 world (a statement that is true, of course, in any modular world as well as in ordinary arithmetic).

The above equation is not the only one that can be found even for the same values of x and y. For instance, consider the following possibilities:

(-3)(3) + (1)(10) = 1

(-13)(3) + (4)(10) = 1

(77)(3) + (-23)(10) = 1

Any of these, plus an infinite number of others, could be used to find the multiplicative inverses of 3 in a mod 10 world or of 10 in a mod 3 world.

As an interesting side note, notice that, just based on the expressions, it
is impossible to discern what the values of *x* and *y* originally
were. As a result, an expression like

(77)(3) + (-23)(10) = 1

tells us not only that -23 and 10 are multiplicative inverses in a modulo 3 world, but also in a modulo 77 world. It also tells us that 23 and -10 are multiplicative inverses in both of those worlds as well.

But does it claim that 77 and 3 are multiplicative inverses in both a mod 10 and a mod -23 world? It would certainly appear so, but what is a mod -23 world? Let's fall back on our basic relationship

ab (mod n)

if and only if

a = Kn + b

for some integer value of *K*.

Notice that the sign of n has no affect on this
relationship since it only changes the sign of *K*, not whether *K* is
an integer or not. Hence the modulo *n* world is identical to the modulo *
-n* world.

We know that, by definition, *y* mod *x* results in a residue *r* such that

y = kx + r

This can be rewritten as

r = y mod x = ax + by

where *a* = -*k* and *b* = 1.

The Euclidean Algorithm tells us that we can continue reducing the successive
residues until we find the GCD of *x* and *y*. If *x* and *y*
are relatively prime, then the GCD will be 1 and, assuming we can keep track of
the appropriate values of *a* and *b*, we will have the information
that we need to find the multiplicative inverses. If, however, *x* and *y*
are not relatively prime, then this process will stop before we reach that point
and this method will fail - however, we already know that for a multiplicative
inverse to exist, *x* and *y* have to be relatively prime.

The only remaining step is to discover how to update the values of *a*
and *b* as we proceed with the Euclidean Algorithm. First, let's slightly
change our nomenclature to the following:

r_{2} = r_{0} mod r_{1} = (a_{2})x
+ (b_{2})y

The idea here is that we will be working with a string of remainders, the
first two of which are *y* and *x* respectively. At each step we will
be producing not only a new remainder, but a new value for *a* and *b*
as well. At any point in the process, we have:

r_{n} = r_{n-2} mod r_{n-1} = (a_{n})x
+ (b_{n})y

As soon as we reach the point were *r*_{n} is equal to 1, then
we are finished and the values a_{n} and b_{n} are the multiplicative inverses we are
seeking. Should *r*_{n} become equal to 0, then we have established
that *x* and *y* are not relatively prime and, hence, that the
multiplicative inverses being sought do no exist.

Since this is a progressive algorithm, at the point we are attempting to find an and bn, we can assume that we still have the values from all prior steps.

From definition of modulo reduction

r_{n-2} = k_{n}r_{n-1} + r_{n}

hence

r_{n} = r_{n-2 }- k_{n}r_{n-1}

But we also know that

r_{n} = (a_{n})x + (b_{n})y

Therefore

r_{n} = [(a_{n-2})x + (b_{n-2})y]_{
}- k_{n}[(a_{n-1})x + (b_{n-1})y]

Reorganizing to collect the coefficients of *x* and *y*
yields

r_{n} = [a_{n-2 }- k_{n}(a_{n-1})]x
+ [b_{n-2 }- k_{n}(b_{n-1})]y

Our update relationships are thereby

a_{n} = a_{n-2 }- k_{n}(a_{n-1})

b_{n} = b_{n-2 }- k_{n}(b_{n-1})

In the Euclidean Algorithm, we didn't care what the value of *
k* was. Here, however, we need to use it as part of updating our coefficient
and so must be sure that we use it correctly. The value of *k*_{n}
is simply the integer quotient when dividing *r*_{n-2} by *r*_{n-1}:

k_{n} = floor(r_{n-1} / r_{n-1})

Since we are going to start at *n*=2, we need a separate
means of finding *a*_{0} and *a*_{1}, as well as *b*_{0}
and *b*_{1}. However, this can be done by inspection since

r_{0} = (a_{0})x + (b_{0})y = y

r_{1} = (a_{1})x + (b_{1})y = x

Therefore *a*_{0} and *a*_{1} are 0
and 1 respectively while *b*_{0} and *b*_{1} are 1 and
0 respectively.

Notice that if all we are interested in finding is the inverse
of *x* modulo *y*, then we do not even need to track the values of *
b*_{n} since *a*_{n} will be the only value of interest
in the end.

Perhaps the easiest way to work the Extended Euclidean Algorithm is to set up a table as follows:

n | r_{n} = r_{n-2} mod r_{n-1} |
k_{n} = floor(r_{n-2} / r_{n-1}) |
a_{n}= a_{n-2} - k_{n}a_{n-1} |

0 | y | -- | 0 |

1 | x | -- | 1 |

2 | |||

3 | |||

4 |

You can then proceed to fill in the table line by line until the value for *
r*_{n} is equal to 1. The value for *a*_{n} on that line
is the multiplicative inverse of *x* modulo *y*. If *r*_{n}
becomes equal to zero first, then no multiplicative inverse exists.

Notice that this algorithm particularly lends itself to a spreadsheet implementation.

- 10
^{-1}mod 77n r _{n}= r_{n-2}mod r_{n-1}k _{n}= floor(r_{n-2}/ r_{n-1})a _{n}= a_{n-2}- k_{n}a_{n-1}0 77 -- 0 1 10 -- 1 2 7 7 -7 3 3 1 8 4 1 2 -23 10

^{-1}mod 77 = -23 mod 77 = 54 - 33 mod 700
n r _{n}= r_{n-2}mod r_{n-1}k _{n}= floor(r_{n-2}/ r_{n-1})a _{n}= a_{n-2}- k_{n}a_{n-1}0 700 -- 0 1 33 -- 1 2 7 21 -21 3 5 4 85 4 2 1 -106 5 1 2 297 33

^{-1}mod 700 = 297 mod 700 = 297 - 72648
^{-1}mod 981623n r _{n}= r_{n-2}mod r_{n-1}k _{n}= floor(r_{n-2}/ r_{n-1})a _{n}= a_{n-2}- k_{n}a_{n-1}0 981623 -- 0 1 72648 -- 1 2 37199 13 -13 3 35449 1 14 4 1750 1 -27 5 446 20 554 6 403 3 -1689 7 46 1 2243 8 35 8 -19633 9 11 1 21876 10 2 3 -85261 11 1 5 448181 72648

^{-1}mod 981623 = 448181 mod 981623 = 448181

The above algorithms are very clean, but they may not be the easiest to remember or derive, should the need to use them arise in a situation in which they can't be looked up. So the question begs to be asked of whether there is a way of deriving the Extended Euclidean Algorithm from scratch in a way that is (relatively) easy to reconstruct without any references. The answer is a yes. Consider the following:

We want to find the multiplicative inverse of *a* (mod *n*). It is
pretty easy to see that:

n 0 * a (mod n)

a 1 * a (mod n)

We want to use this as our starting point and eventually get to an equation of the form:

1 b * a (mod n)

At which point, if we are successful, we know that *b* is the
multiplicative inverse of *a* (mod *n*).

So that we can produce an algorithm that will work at any step in the
process, let's write this for any two generic numbers, *x* and *y*, in
a mod *n* world

x
k_{x} * a (mod n)

y
k_{y} * a (mod n)

Looking at just the left hand side, what if we reduce the first equation by
the second? This means we are looking for the value *z* such that

x = Q*y + z

This means that

z = x - Q*y

Now substitute the right hand sides of the original equations into the above and we have:

z
[k_{x}
* a] - Q*[k_{y} * a] (mod n)

Collecting terms, we have

z
(k_{x}
- Q*k_{y}) * a (mod n)

The result is, not surprisingly, that when we reduce the first equation by
the second, the coefficient of *a* becomes the coefficient of *a* from
the first equation less *Q* times the coefficient of *a* from the
second equation where *Q* is the integer quotient of the value on the
left-hand side of the first equation divided by the value on the left-hand side
of the second.

Putting it in explicit terms:

Given the two prior entries in our table:

r_{(i-2)}
k_{(i-2)} * a (mod n)

r_{(i-1)}
k_{(i-1)} * a (mod n)

The next entry is:

r_{(i)}
k_{(i)} * a (mod n)

Where

r_{(i)} = r_{(i-2)}
mod r_{(i-1)}

k_{(i)}
k_{(i-2)} - (Q_{(i)}*
k_{(i-1)}) (mod n)

Where

Q_{(i)} = floor(r_{(i-2)}
/ r_{(i-1)})

Let's illustrate this by finding the multiplicative inverse of 13 modulo 60.

i r _{i}= r_{i-2}mod r_{i-1}Q _{i}= floor(r_{i-2}/ r_{i-1})k _{i}k_{i-2}- Q_{i}k_{i-1}(mod n)0 60 -- 0 1 13 -- 1 2 8 4 0 - 4*1 56 3 5 1 1 - 1*56 5 4 3 1 56 - 1*5 51 5 1 1 5 - 1*51 37

Therefore 37 is the multiplicative inverse of 13 modulo 60, which can be verified directly since

37*13 = 8*60 + 1

As before, the process is continued until the entry in the leftmost column is either 1 or 0. If an entry of 0 is reached (before an entry of 1) then no multiplicative inverse exists.

Notice that this is almost, but not quite, the same as the
algorithm in the prior examples. The difference is that, developed this way, our
coefficients of *a* (the rightmost column) are in a mod *n* world at
each step instead of just at the end. This is perfectly legitimate, although it
robs us of some information. But this is not important since it is information
we do not need to answer the question at hand.