Division Modulo n

Let n and d be positive numbers whose greatest common factor is 1; then the congruence

dx ≡ a (mod n)

has a solution, which is unique modulo n. How can we prove this - and while we're at it, how can we find x with reasonable efficiency?

A preliminary exercise

We might want to begin be being sure that the greatest common factor of n and d really is 1. There is an old method, usually called Euclid's algorithm, for finding the greatest common factor of two positive numbers A and B.

Let us suppose that A > B. (This costs us nothing; if necessary we just swith the two numbers around.) We might try to divide A by B. If there is no remainder, then obviously the greatest common factor is B and we are done. What if there is a remainder? Then

A = kB + R

where

0 ≤ R < B .

Now any common factor of A and B is a factor of R; and any common factor of B and R is a factor of A. So, the greatest common factor of A and B is also the greatest common factor of B and R.

And that's the ball game.

Because that reduces the problem for A and B to the problem for the smaller numbers B and R. We repeat as often as needed, squeezing the numbers down until we are left with the greatest common factor.

Let's look at an example: find the greatest common factor of 60 and 37. Divide 60 by 37:

60 = 1 × 37 + 23 .

There is a remainder; so now we look at the numbers 37 and 23:

37 = 1 × 23 + 14 .

And again:

23 = 1 × 14 + 9 .
14 = 1 × 9 + 5 .
9 = 1 × 5 + 4 .
5 = 1 × 4 + 1 .

At this point we can stop: 1 is the highest common factor.

Solving the congruence

The same calculation that we can use to verify that n and d have greatest common factor 1 can be extended to solve the congruence equation dx ≡ a (mod n). The trick is to realize that we actually know two congruence equations:

nx &equiv 0 (mod n) ,
dx &equiv a (mod n) .

Now, if d > 1, we divide n by d and notice the remainder: n = kd + r, where 0 ≤ r < d. Another way of putting it is n - kd = r. Thus, if we subtract k times the second equation from the first, we obtain another equation with a smaller coefficient on the left-hand side:

(n - kd)x &equiv (0 - ka) (mod n) , or
rx &equiv b (mod n) .

To keep the arithmetic from getting unwieldy, we might as well replace (0 - ka) by a number b which is congruent to it modulo n, and in the range from 0 to n. We now have two smaller congruences:

dx &equiv a (mod n) ,
rx &equiv b (mod n) .

We reduce these in the same way, until we have a congruence that is the solution to the problem.

Let's look at an example: 37x ≡ 11 (mod 60). We set up two congruences, and then reduce them. Note that at each stage we use the latest two partial results.

60x &equiv 0 (mod 60)
37x &equiv 11 (mod 60) .

Then

(60 - 37)x &equiv (0 - 11) (mod 60) , that is,
23x &equiv 49 (mod 60) .

Now we have

37x &equiv 11 (mod 60)
23x &equiv 49 (mod 60) .

From these we find

(37 - 23)x &equiv (11 - 49) (mod 60) , that is,
14x &equiv 22 (mod 60) .

Resist the temptation to divide by 2, which is not relatively prime to 60. Instead, press onward:

23x &equiv 49 (mod 60)
14x &equiv 22 (mod 60)

imply

9x &equiv 27 (mod 60) .

The next step is

5x &equiv 55 (mod 60) ,

and then

4x &equiv 32 (mod 60) ,

and finally

x &equiv 23 (mod 60) .

I dare not omit checking my arithmetic: 37×23 = 851 ≡ 11 (mod 60).

Last modified on $Date: 2007-04-19 22:46:45 -0400 (Thu, 19 Apr 2007) $

Christopher J. Henrich