# 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 *a* – *b*. 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* = *a* – *qb*. If *n* ≠ 0, and *x* divides *a – qb*, then *x* divides *r*. We have now ...

Get *Introduction to Computer Security* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.