The Euclidean Algorithm for Large Numbers, Theory

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.
  • 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').