# 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 (the 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. We will also explain why it is working.
• This algorithm involves the operation of dividing and calculating remainders.
• 'a' and 'b' are the two positive integers, 'a' >= 'b'.
• Divide 'a' by 'b' and get the remainder, 'r'.
• If 'r' = 0, STOP. 'b' = the GCF (HCF, GCD) of 'a' and 'b'.
• Else: Replace ('a' by 'b') & ('b' by 'r'). Return to the division step above.

### Let's calculate the greatest common factor GCF (the 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.

### 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.

### Why is the answer a factor (a divisor) of the initial 'a' and 'b'?

• Note: 'a' ÷ 'b' = 'q' + 'r' is equivalent to the equation: 'a' = 'q' × 'b' + 'r', where 'q' is the quotient of the operation.
• When the final value of 'r' = 0, the final value of 'b' is a factor (a divisor) of the final value of 'a', since 'a' = 'q' × 'b' + 0.
• Go backwards the previous division steps, through each equation, 'a' = 'q' × 'b' + 'r', and notice that at each step the final value of 'b' is a factor (a divisor) of each value of 'r' and of each value of 'b' and therefore is a factor of each value of 'a'. So the final value of 'b', which is the last remainder in our list that is not zero, is a factor of the initial values of ('a' and 'b'), or in other words, is a divisor of the intial values of ('a' and 'b').

### Why is the answer equal to the CGF (HCF, GCD)?

• Look at all the equations: 'a' = 'q' × 'b' + 'r'. As we saw above, the final value of 'b' is a factor of all the values of 'a', 'b', and 'r'.
• Therefore the final value of 'b' must also be a factor of the last value of 'r', the one that is not zero. And the final value of 'b' couldn't be larger than that value. But the final value of 'b' is actually equal to that value of 'r', therefore the final value of 'b' is the largest factor (divisor) of the initial values of 'a' and 'b'. And by definition it's called the greatest (highest) common factor (divisor) of numbers.

### 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.

### Proof for the LCM formula

• Least common multiple, formula: lcm (a; b) = (a × b) / gcf, hcf, gcd (a; b);
• Let's say that the prime factorizations of 'a' and 'b' are:
• a = m × n × p, where m, n, p - any prime numbers
• b = m × q × t, where m, q, t - any prime numbers
• => lcm (a; b) = m × n × p × q × t;
• => gcf, hcf, gcd (a; b) = m;
• Therefore:
• (a × b) / gcf, hcf, gcd (a; b) =
• (m × m × n × p × q × t) / m =
• m × n × p × q × t =
• lcm (a; b).