Euclidean Algorithm for Large Numbers, a Method of Computing GCF, LCM

A method of computing the greatest common factor, GCF (also called the greatest common divisor, GCD, or the highest common factor, HCF) of large numbers


For large numbers, the prime factorization process is difficult and lengthy. If you need to determine the greatest common factor, GCF (greatest common divisor, GCD, or HCF) of such large numbers, then use a method that is different from the prime factorization: use the Euclid's algorithm... Have a look at the example below.

Let's calculate the greatest common factor GCF (greatest common divisor, GCD, HCF) of the numbers 53,667 and 25,527 by using the Euclid's algorithm:

The greatest common factor GCF (or greatest common divisor, GCD, HCF) of the numbers is the last remainder that is not zero.

If this remainder is equal to 1, then the two tested numbers are coprime - they don't have any common factor other than 1.

201 is the largest divisor or largest factor (GCF, GCD) of the numbers 53,667 and 25,527.

Using Euclid's algorithm, we can determine whether or not two numbers are coprime.

Let's calculate the greatest common factor, GCF (greatest common divisor, GCD) of (87; 41) by using Euclid's algorithm:

The last remainder of the operations above, not zero, is equal to 1, so GCF (87, 41) = 1 => the numbers are coprime.

Euclid's algorithm for more than two numbers:

Euclid's algorithm can also be used for finding the greatest common factor, GCF (greatest common divisor, GCD, HCF) of several numbers, such as a, b and c. We will proceed in stages. First we find GCF (a; b) = d and then we find GCF (c; d) = e

Euclid's algorithm: find the least common multiple, LCM (also called lowest common multiple, or smallest common factor), of large numbers


In the case of large numbers it becomes inconvenient to calculate the least common multiple, LCM, since prime factorization takes time.

Using Euclid's algorithm for finding the greatest common factor, GCF (greatest common divisor, GCD, HCF) solves our problem - see the example above, but it also does it for the least common multiple, LCM, according to the formula:

LCM (a, b) = (a × b) / GCF (a; b);

This method may not be extended for more than two numbers.


What is a prime number?

What is a composite number?

Prime numbers up to 1,000

Prime numbers up to 10,000

Sieve of Eratosthenes

Euclid's algorithm

Simplifying ordinary (common) math fractions (reducing to lower terms): steps to follow and examples