document.write (document.title)

 Math Help > Number Theory > Chinese Remainder Theorem > Extended Euclidean Algorithm

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

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

 a = b = r s ck=dk-2/dk-1 d=remainder

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.

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