A method of computing (finding) the greatest common factors (gcf) of large numbers
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 indicated. The Euclidean Algorithm is such a method for calculating the gcf.
Have a look at the example below. We will also explain why it's working.
Note: The greatest common factor (gcf) is also called the highest common factor (hcf), or the greatest common divisor (gcd).
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.
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.