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?

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

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 ≡ 0 (mod n) ,

dx ≡ 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 ≡ (0 - ka) (mod n) ,
or

rx ≡ 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 ≡ a (mod n) ,

rx ≡ 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 ≡ 0 (mod 60)

37x ≡ 11 (mod 60) .

Then

(60 - 37)x ≡ (0 - 11) (mod 60)
, that is,

23x ≡ 49 (mod 60) .

Now we have

37x ≡ 11 (mod 60)

23x ≡ 49 (mod 60)
.

From these we find

(37 - 23)x ≡ (11 - 49) (mod 60)
, that is,

14x ≡ 22 (mod 60) .

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

23x ≡ 49 (mod 60)

14x ≡ 22 (mod 60)

imply

9x ≡ 27 (mod 60)
.

The next step is

5x ≡ 55 (mod 60)
,

and then

4x ≡ 32 (mod 60)
,

and finally

x ≡ 23 (mod 60)
.

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