### The problem

The problem: find the "modular reciprocal" -- that is, given coprime a and b,
find c such that ac=1 (mod b).

You could say c = 1/a (mod b), in other words c is the "modular reciprocal"
of a (mod b).

Another way to look at the question is based on the Euclidean Algorithm
Property, a.k.a. B�zout's Identity, which states

For any integers a and b, there exist integers x and y such that
GCD(a,b)=ar+bs.

Here, ar+bs = 1, so ar=1 (mod b). That means r is the modular
reciprocal of a (mod b).

### Extended Euclidean Algorithm

In this example, we will start with given values of a and b. Then we
will find successive values of r, s, and d such that ar+bs=d. Furthermore,
the values of d will be steps in the ordinary Euclidean algorithm for finding
the GCD of a and b. The final result, where d=1, will give us the values
of r and s we are seeking.

In each step, c_{k}=d_{k-2}/d_{k-1}, and d_{k}
is the remainder of that division. The r and s values are calculated as r_{k}=r_{k-2}-c_{k}r_{k-1},
and s_{k}=s_{k-2}-c_{k}s_{k-1}.

This works because d_{k}=d_{k-2}-c_{k}d_{k-1}.
That is, each of r, s, and d can be seen as the same linear combination of the
two values above it.

### JavaScript Modular Reciprocal Calculator

Here is a very simple JavaScript calculator that you can use to understand
the algorithm. If you find the row that contains d=1, then that value of r
will be the one for which ar+bs=1. Thus 1/a = r (mod b), and 1/b = s (mod
a).

### Glossary

**pairwise coprime** - a set of integers is pairwise coprime if no two
elements of the set share any factor other than 1 or -1. (Note: 1 is
coprime to every integer by this definition.)

### Internet references

Wikipedia:
Extended Euclidean algorithm

### Related Pages in this website

Number Theory Definitions --
Particularly the Euclidean Algorithm Property, a.k.a. B�zout's Identity.

Euclidean algorithm

The webmaster and author of this Math Help site is
Graeme McRae.