## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# Chapter 28. The Extended Euclidean Algorithm

The Extended Euclidean Algorithm is a staple of number theory and is used to solve equations of the form ax mod n = b. This chapter reviews this algorithm and its applications. We begin with the classical algorithm and then extend it to solve simple equations.

# The Euclidean Algorithm

Euclid's algorithm determines the greatest common divisor of two integers. The algorithm is based on the observation that, if x divides both a and b, then x divides their difference ab. The trick is to find the largest such x.

Assume (without loss of generality) that a > b. If x divides a – b, then it also divides a – qb, where q is an integer. Let r = aqb. If n ≠ 0, and x divides a – qb, then x divides r. We have now ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required