chapter  3
22 Pages

Euclidean Algorithm

The Euclidean algorithm was stated by Euclid in his Elements over 2000 years ago. It is still the most efficient way to find the greatest common divisor of two integers.

Before investigating the Euclidean algorithm, we take a look at the mod function. This function can be used to define modular arithmetic, which is used extensively in applied algebra.