8 - Euclid's Algorithm

Summary

In Section 4.3.3 of Chapter 4, we introduced the notion of modular multiplicative inverses: for a modulus m, two integers a and b are mod-m multiplicative inverses if a · b ≡ 1 (mod m). In Section 4.3.4, we demonstrated a method for finding mod-m multiplicative inverses: write down the mod-m multiplication table for all mod-m representatives, and search for ones in the table. In Section 4.3.5, we observed that, for the modulus 6, some integers don't have multiplicative inverses, even integers that are not congruent mod-6 to 0. The method we present in this chapter will explain this phenomenon.

In this chapter, we describe a good algorithm for calculating modular multiplicative inverses. The algorithm is an extension of one attributed to the classical mathematician Euclid, who supposedly lived around 300 B.C. He is known primarily for his contribution to and systematization of geometry, but his famous book Elements also addressed number theory.

The measuring puzzle

Suppose you are given two containers and told how many cups of water each one can hold. You are also given an empty basin that can hold an unlimited amount of water. What is the smallest positive number of cups you can leave in the basin by using these two containers? The rules of the puzzle allow you to fill either container with water either from the tap or the basin, and to pour the water from the container either down the drain or into the basin.