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_kr_k-1, and s_k=s_k-2-c_ks_k-1.

This works because d_k=d_k-2-c_kd_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).

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]