## 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' × 'q
_{1}' + 'r_{1}', 'r_{1}' not zero. - 2. Step: 'b' = 'r
_{1}' × 'q_{2}' + 'r_{2}', 'r_{2}' not zero. - 3. Step: 'r
_{1}' = 'r_{2}' × 'q_{3}' + 'r_{3}', 'r_{3}' 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)}' × 'q_{n}' + 'r_{n}', 'r_{n}' = zero. - The remainder is zero, so we stop.

- If 'r
_{n}' = 0 => according to the n^{th}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 3
^{rd}step: 'r_{(n-1)}' is a factor of both 'r_{3}' and 'r_{2}', so it is also a factor of 'r_{1}'. - According to the 2
^{nd}step: 'r_{(n-1)}' is a factor of both 'r_{2}' and 'r_{1}', so it is also a factor of 'b'. - According to the 1
^{st}step: 'r_{(n-1)}' is a factor of both 'r_{1}' 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 1
^{st}division step: If 't' is a factor of both 'a' and 'b', then it is also a factor of 'r_{1}'. - According to the 2
^{nd}division step: If 't' is a factor of both 'b' and 'r_{1}', then it is also a factor of 'r_{2}'. - 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').