Euclidean algorithm for large numbers: method of computing the greatest common factor, GCF (divisor, GCD, HCF) and the least common multiple, LCM

Tutoring: Euclid's algorithm: a method of computing the greatest common factor, GCF (also called the greatest common divisor, GCD, or the highly 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:

  • 1) 53,667 = 25,527 × 2 + 2,613 (divide the larger number by the smaller one)
  • 2) 25,527 = 2,613 × 9 + 2,010 (divide the smaller number by the above operation's remainder)
  • 3) 2,613 = 2,010 × 1 + 603 (divide the 1st operation's remainder above by the 2nd operation's remainder)
  • 4) 2,010 = 603 × 3 + 201 (divide the 2nd operation's remainder by the 3rd operation's remainder)
  • 5) 603 = 201 × 3 + 0 (divide the 3rd operation's remainder by the 4th operation's remainder); at this step, the remainder is zero, so we stop, 201 is the number we were looking for.

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:

  • 1) 87 = 41 × 2 + 5 (divide the bigger number by the smaller one)
  • 2) 41 = 5 × 8 + 1 (divide the smaller number by the remainder from the above operation)
  • 3) 5 = 5 × 1 + 0 (divide the remainder from the 1st operation by the remainder from the 2nd operation, which is equal to 1; this operation will produce a remainder equal to zero.

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

Tutoring: 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 math fractions (reducing to lower terms): steps to follow and examples