1 (mod n)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:
r2 = r0 mod r1 = (a2)x + (b2)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:
rn = rn-2 mod rn-1 = (an)x + (bn)y
As soon as we reach the point were rn is equal to 1, then we are finished and the values an and bn are the multiplicative inverses we are seeking. Should rn 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
rn-2 = knrn-1 + rn
hence
rn = rn-2 - knrn-1
But we also know that
rn = (an)x + (bn)y
Therefore
rn = [(an-2)x + (bn-2)y] - kn[(an-1)x + (bn-1)y]
Reorganizing to collect the coefficients of x and y yields
rn = [an-2 - kn(an-1)]x + [bn-2 - kn(bn-1)]y
Our update relationships are thereby
an = an-2 - kn(an-1)
bn = bn-2 - kn(bn-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 kn is simply the integer quotient when dividing rn-2 by rn-1:
kn = floor(rn-1 / rn-1)
Since we are going to start at n=2, we need a separate means of finding a0 and a1, as well as b0 and b1. However, this can be done by inspection since
r0 = (a0)x + (b0)y = y
r1 = (a1)x + (b1)y = x
Therefore a0 and a1 are 0 and 1 respectively while b0 and b1 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 bn since an 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 | rn = rn-2 mod rn-1 | kn = floor(rn-2 / rn-1) | an= an-2 - knan-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 rn is equal to 1. The value for an on that line is the multiplicative inverse of x modulo y. If rn becomes equal to zero first, then no multiplicative inverse exists.
Notice that this algorithm particularly lends itself to a spreadsheet implementation.
| n | rn = rn-2 mod rn-1 | kn = floor(rn-2 / rn-1) | an= an-2 - knan-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
| n | rn = rn-2 mod rn-1 | kn = floor(rn-2 / rn-1) | an= an-2 - knan-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
| n | rn = rn-2 mod rn-1 | kn = floor(rn-2 / rn-1) | an= an-2 - knan-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
kx * a (mod n)
y
ky * 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
[kx
* a] - Q*[ky * a] (mod n)
Collecting terms, we have
z
(kx
- Q*ky) * 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 ri = ri-2 mod ri-1 Qi = floor(ri-2 / ri-1) ki 0 60 -- 0 1 13 -- 1 2 8 4 0 - 4*1 3 5 1 1 - 1*56 4 3 1 56 - 1*5 5 1 1 5 - 1*51
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.