Euclidean Algorithm

Definition

Euclidean Algorithm

Let , then the Euclidean algorithm can be used to compute the greatest common divisor of :

The algorithm terminates at . The result of the algorithm is .