The Euclidean algorithm for large numbers - a calculation method of the greatest (highest) common factor (divisor), gcf (hcf, gcd), and the least common multiple, lcm; LCM (a; b) = (a × b) / gcf (a; b) - theory, examples and explanations

A method of computing (finding) the greatest common factors (gcf) of large numbers


Let's see what the greatest common factor (gcf) of the numbers 53,667 and 25,527 is:

The greatest common factor of the two numbers is the last non-zero remainder.

Calculate the gcf (87, 41):

But why is the number thus obtained a divisor of the initial values 'a' and 'b'?

Why is the number obtained this way always equal to the greatest common factor, gcf?

How to use the Euclidean algorithm for more than two numbers:

The Euclidean Algorithm: Calculate the Least Common Multiple (lcm) for large numbers


Proof of the lcm formula

Some articles on the prime numbers

What is a prime number? Definition, examples

What is a composite number? Definition, examples

The prime numbers up to 1,000

The prime numbers up to 10,000

The Sieve of Eratosthenes

The Euclidean Algorithm

Completely reduce (simplify) fractions to the lowest terms: Steps and Examples