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).
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, ck=dk-2/dk-1, and dk is the remainder of that division. The r and s values are calculated as rk=rk-2-ckrk-1, and sk=sk-2-cksk-1.
This works because dk=dk-2-ckdk-1. That is, each of r, s, and d can be seen as the same linear combination of the two values above it.
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.)
Wikipedia: Extended Euclidean algorithm
Number Theory Definitions -- Particularly the Euclidean Algorithm Property, a.k.a. B�zout's Identity.
The webmaster and author of this Math Help site is Graeme McRae.