# 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

• Note: The greatest common factor (gcf) is also called the highest common factor (hcf), or the greatest common divisor (gcd).
• For large numbers, the prime factorization process is lengthy and difficult. If we needed to calculate the greatest common factor (gcf) for such large numbers, then a method that is not based on the prime factorization of the numbers would be more than welcome. The Euclidean Algorithm is one such method for calculating the gcf. Have a look at the example below. We will also explain why it is working.
• This algorithm starts by dividing the numbers and recording the remainder of the operation.
• If 'a' and 'b' are the two positive integers, 'a' >= 'b'.
• Divide 'a' by 'b' and get the remainder, 'r'.
• If 'r' = 0, STOP. 'b' is the gcf of 'a' and 'b'.
• Else: Replace ('a' by 'b') and ('b' by 'r'). Return to the step above.

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

• [1] Start by dividing the larger number by the smaller:
• 53,667 ÷ 25,527 = 2 and the Remainder = 2,613 => 53,667 = 25,527 × 2 + 2,613
• [2] Then divide the smaller number by the remainder from the above operation:
• 25,527 ÷ 2,613 = 9 and the Remainder = 2,010 => 25,527 = 2,613 × 9 + 2,010
• [3] Divide the remainder of the first operation by the remainder of the second operation:
• 2,613 ÷ 2,010 = 1 and the Remainder = 603 => 2,613 = 2,010 × 1 + 603
• [4] Divide the remainder of the second operation by the remainder of the third operation:
• 2,010 ÷ 603 = 3 and the Remainder = 201 => 2,010 = 603 × 3 + 201
• [5] Divide the remainder of the third operation by the remainder of the fourth operation:
• 603 ÷ 201 = 3 and the Remainder = 0 => 603 = 201 × 3
• At this step, the remainder is zero, so we stop: 201 is the number we were looking for.
• Wrapping up:
• 201 is the last non-zero remainder. This is the greatest common factor, gcf, of the numbers.

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

• If this last remainder is equal to 1, then the two numbers are relatively prime (coprime).
• For the above operations, the last non-zero remainder, 201, is the greatest common factor (gcf) of the numbers 53,667 and 25,527.
• By using the Euclidean algorithm we can prove that two numbers are relatively prime, see the example below.

### Calculate the gcf (87, 41):

• [1] Start by dividing the larger number by the smaller:
• 87 ÷ 41 = 2 and the Remainder = 5 => 87 = 41 × 2 + 5
• [2] Then divide the smaller number by the remainder from the above operation:
• 41 ÷ 5 = 8 and the Remainder = 1 => 41 = 5 × 8 + 1
• [3] Divide the remainder of the first operation by the remainder of the second operation:
• 5 ÷ 1 = 5 and the Remainder = 0 => 5 = 1 × 5 + 0
• The last non-zero remainder from the above operations is equal to 1.
• gcf (87, 41) = 1, so the numbers are relatively prime.

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

• Note: The division 'a' ÷ 'b' = 'q' + 'r' corresponds to the equation: 'a' = 'b' × 'q' + 'r', where 'q' is the quotient of the division.
• If the last value of 'r' = 0, then the last value of 'b' is a divisor of the last value of 'a' since 'a' = 'b' × 'q' + 0.
• Let's calculate the gcf (a, b):
• 1. Step: 'a' = 'b' × 'q1' + 'r1', 'r1' not zero.
• 2. Step: 'b' = 'r1' × 'q2' + 'r2', 'r2' not zero.
• 3. Step: 'r1' = 'r2' × 'q3' + 'r3', 'r3' not zero.
• ...
• (n-3). Step: 'r(n-5)' = 'r(n-4)' × 'q(n-3)' + 'r(n-3)', 'r(n-3)' not zero.
• (n-2). Step: 'r(n-4)' = 'r(n-3)' × 'q(n-2)' + 'r(n-2)', 'r(n-2)' not zero.
• (n-1). Step: 'r(n-3)' = 'r(n-2)' × 'q(n-1)' + 'r(n-1)', 'r(n-1)' not zero.
• n. Step: 'r(n-2)' = 'r(n-1)' × 'qn' + 'rn', 'rn' = zero.
• The remainder is zero, so we stop.
• If 'rn' = 0 => according to the nth step: 'r(n-1)' is a factor of 'r(n-2)'.
• 'r(n-1)' is also the last non-zero remainder.
• According to the (n-1)th step: 'r(n-1)' is a factor of both 'r(n-1)' (the number itself) and 'r(n-2)', so it is also a factor of 'r(n-3)'.
• According to the (n-2)th step: 'r(n-1)' is a factor of both 'r(n-2)' and 'r(n-3)', so it is also a factor of 'r(n-4)'.
• According to the (n-3)th step: 'r(n-1)' is a factor of both 'r(n-3)' and 'r(n-4)', so it is also a factor of 'r(n-5)'.
• ...
• According to the 3rd step: 'r(n-1)' is a factor of both 'r3' and 'r2', so it is also a factor of 'r1'.
• According to the 2nd step: 'r(n-1)' is a factor of both 'r2' and 'r1', so it is also a factor of 'b'.
• According to the 1st step: 'r(n-1)' is a factor of both 'r1' and 'b', so it is also a factor of 'a'.
• So, we have just shown that the last non-zero remainder, r(n-1), is a factor of both 'a' and 'b'.

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

• As we saw above, the final non-zero remainder evenly divides both 'a' and 'b'. Let's call this factor 't'.
• According to the 1st division step: If 't' is a factor of both 'a' and 'b', then it is also a factor of 'r1'.
• According to the 2nd division step: If 't' is a factor of both 'b' and 'r1', then it is also a factor of 'r2'.
• And so on, up to the (n-1)th step: If 't' is a factor of 'r(n-3)' and 'r(n-2)', then it is also a factor of 'r(n-1)'. But as we calculated above, this factor is the last non-zero remainder, which in our case is 'r(n-1)'.
• So 't' couldn't be larger than 'r(n-1)' since it has to be a factor of it.

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

• The Euclidean algorithm can also be used to find the greatest common factor of multiple numbers, more than two, such as 'a', 'b', and 'c'.
• First calculate the gcf ('a', 'b') = 'd' and after that calculate the gcf ('c', 'd').

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

• For very large numbers, it becomes impractical to calculate the least common multiple (lcm) because getting the prime factorization of those numbers takes too long.
• With the help of the Euclidean algorithm not only the greatest common factor (gcf) is to be found - as seen above, but also the least common multiple (lcm) is calculated according to the formula:
• #### lcm ('a', 'b') = ('a' × 'b') / gcf ('a', 'b')

• This method can be used when there are no more than two numbers.

### Proof of the lcm formula

• Suppose the prime factorizations of 'a' and 'b' are:
• 'a' = 'm' × 'n' × 'p', where 'm', 'n', 'p' are any prime numbers.
• 'b' = 'm' × 'q' × 't', where 'm', 'q', 't' are any prime numbers.
• => lcm ('a', 'b') = 'm' × 'n' × 'p' × 'q' × 't'
• => gcf ('a', 'b') = 'm'
• Therefore:
• ('a' × 'b') / gcf ('a', 'b') =
• ('m' × 'm' × 'n' × 'p' × 'q' × 't') / 'm' =
• 'm' × 'n' × 'p' × 'q' × 't' =
• lcm ('a', 'b').