# Modular Inverses

The modular inverse of a with respect to n is the number b such that a × b ≡ 1 (modulo n).

For example, 5 × 26 = 130. Now 130 ≡ 1 (modulo 43) because 130 = 3×43 + 1. So the inverse of 5 with respect to 43 is 26. Conversely, the inverse of 26 is 5.

#### Simple Searching

For small numbers, we can find the inverse by simple searching. If for example we want to find the inverse of 5 with respect to 43, one way is to write down multiples of 5. Remember to wrap around so that if the number gets greater than or equal to 43, you subtract 43 to keep it in the range 0 - 42. The multiple of 5 after 40 is written as 2 rather than 45.

5 10 15 20 25 30 35 40 2 7 12 17 22 27 32 37 42
4 9 14 19 24 29 34 39 1 6 11 16 21 26 31 36 41
3 8 13 18 23 28 33 38 0

Notice that every number from 0 to 42 appears in this list once and once only. The one that we are looking for is the 26th number in the list, so 5 × 26 is equal to 1 (modulo 43).

This is obviously a cumbersome method since it would take a very long time if the number n was very large.

#### Does every number have a modular inverse?

If we try to find the inverse of 35 with respect to 112, we can write out the multiples of 35, remembering to subtract 112 if the result gets above 112:

35 70 105 28 63 98 21 56 91 14 49 84 7 42 77 0 35 ...

Since we've looped around to 35, this pattern will obviously repeat, but will never reach 1. The reason is that 35 is equal to 5×7 while 112 is equal to 16×7. Because both numbers share 7 as a factor, the list of multiples of 35 will repeat after 112/7 which is 16, so it will never go through all the possible values and will never reach 1.

So if we want the number a to actually have a modular inverse with respect to n, it must share no common factors with n.

#### An Algorithm

What we're actually looking for is a solution to the equation:

5 × b = c × 43 + 1

for some values b and c. These variables are constrained to being integers, so this is a Diophantine Equation. There is a recognised method of tackling these and it gives rise to the following algorithm:

#### To find the modular inverse of a with respect to n:

Write a column of numbers with n at the top and a below it. Divide n by a and get the remainder. Write this under the other two numbers. Now repeat - take the number which is second from the bottom in the column, divide it by the number at the bottom and record the remainder below this at the bottom of the column. We stop this process when we reach 1. So for example if the two numbers are 1000001 and 90125 (the title of a Yes album), then the column will look like this:

 1000001 90125 8626 3865 896 281 53 16 5 1

Next we write a second column beside this: write a plus sign + at the top of the column beside the number a. Below this, write a minus sign - then continue down the column alternating + and - signs. We now have:

 1000001 + 90125 - 8626 + 3865 - 896 + 281 - 53 + 16 - 5 + 1 -

We now build the third column, which is the most difficult part of the algorithm. Put 1 in the last position, opposite the 1 in the first column. Then fill in the figures upwards. Each value is calculated from the figure below it and the figures in the first column as follows:

If there's a + beside it, then:

Multiply the figure below the space you're filling by the figure to the left of the space, add 1, then divide by the figure below and to the left of the space.

If there's a - beside it, then:

Multiply the figure below the space you're filling by the figure to the left of the space, subtract 1, then divide by the figure below and to the left of the space.

To fill the first space, we multiply the 1 below the space by the 5 to the left of it to get 5. We add 1, then divide by the 1 in the first column to get 6. Here we show the 1 at the bottom and the 6 filled in above it:

 1000001 + 90125 - 8626 + 3865 - 896 + 281 - 53 + 16 - 5 + 6 1 - 1

Now we'll fill in the space in the third cell from the bottom. Take the 6 below it, multiply it by the 16 to the left of it to get 96, subtract 1 to get 95, then divide by the 5 that is to the left and below it to get 19:

 1000001 + 90125 - 8626 + 3865 - 896 + 281 - 53 + 16 - 19 5 + 6 1 - 1

With all the values in the column filled in, we get:

 1000001 + 1188617 90125 - 107124 8626 + 10253 3865 - 4594 896 + 1065 281 - 334 53 + 63 16 - 19 5 + 6 1 - 1

The top number in the third column is one possible answer. Sometimes, as in this case, this process will return a value which is bigger than the initial number a. We should always take the result modulo a to get the smallest possible positive answer. In this case, it gives us 188616. We can check this by multiplying our original number 90125 by 188616. We get 16999017000 which is equal to 16999×1000001 + 1.

#### Efficiency

This method works, but I have a feeling that it is not efficient. We're dividing numbers to construct the column on the left, but we're both multiplying and dividing to construct the column on the right. So for example we divide by 53 to get the 16 on the left, but we also multiply by 53 and divide by 53 at separate times in constructing two of the numbers in the right column. Is there some redundancy here? While a few extra multiplications and divisions doesn't sound like a big deal, we'd like an algorithm that could be used on large numbers where multiplications and divisions are computing-intensive, for example 100-digit numbers.