Euclidean algorithm

Previous: Algorithm

The Euclidean algorithm or Euclid’s algorithm is for efficiently finding the greatest common divisor of two numbers. The idea of the algorithm is based on the observation that, if r is the remainder when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r. This we can use the equation: GCD(a,b) == GCD(b,r).