### III.22 The Euclidean Algorithm and Continued Fractions

*Keith Ball*

### 1 The Euclidean Algorithm

THE FUNDAMENTAL THEOREM OF ARITHMETIC [V.14], which states that every integer can be factored into primes in a unique way, has been known since antiquity. The usual proof depends upon what is known as the Euclidean algorithm, which constructs the highest common factor *(h,* say) of two numbers *m* and *n*. In doing so, it shows that *h* can be written in the form *am + bn* for some pair of integers *a, b* (not necessarily positive). For example, the highest common factor of 17 and 7 is 1, and sure enough we can express 1 as the combination 1 = 5 × 17 - 12 × 7.

The algorithm works as follows. Assume that *m* is larger than *n* and start by dividing *m* by *n* to yield a ...