# Greatest common divisor (GCF)  The greatest common divisor (GCF) is the largest number by which two or more numbers can be divided. This, without leaving any residue.

That is, the greatest common divisor or GCF is the highest figure by which a set of numbers can be divided, resulting in a whole number.

A divisor can be formally defined as that number that is contained in another exactly an amount n times.

It should be noted that the numbers on which the GCF is calculated must be nonzero.

To explain it better, let’s look at an example. Suppose we have 35 and 15. Thus, we observe what the divisors of each are:

• Divisors of 35 → 35,7,5,1
• Divisors of 15 → 15,5,3,1

Therefore, the greatest common factor of 35 and 15 is 5.

It is worth mentioning that if the common divisors of two numbers are only 1 and -1, they are called "prime to each other."

## Methods to calculate the greatest common divisor

We can distinguish the following three methods to calculate the greatest common divisor:

• Decomposition into prime factors: Numbers are decomposed into prime numbers. Then, to calculate the GCF, we take the common numbers raised to the lowest power. For example, suppose we have 216 and 156:

216/2 = 108

108/2 = 54

54/2 = 27

27/3 = 9

9/3 = 3

3/3 = 1

216 = (3 ^ 3) * (2 ^ 3)

156/2 = 78

78/2 = 39

39/3 = 13

13/13 = 1

156 = 13 * 3 * (2 ^ 2)

Therefore, the greatest common divisor between both numbers would be: (2 ^ 2) * 3 = 12

Now suppose we have three elements: 315, 441 and 819

315 = (3 ^ 2) * 7 * 5

441 = (3 ^ 2) * (7 ^ 2)

819 = (3 ^ 2) * 7 * 13

Then, after disaggregating them, taking each divisor with its lowest power, the result would be:

GCF = (3 ^ 2) * 7 = 63

• Euclid’s algorithm : By dividing a by b , we obtain a quotient c and r . So, the greatest common divisor of a and b is the same as that of b and r . This, given the following: a = bc + r . To understand it better, let’s apply this method to the example shown previously with 216 and 156.

216/156 = 1 with remainder of 60

now we divide 156/60 = 2 with remainder 36

We divide 60/36 = 1 again with remainder 24

Once again we divide 36/24 = 1 with remainder 12

And finally we divide 24/12 = 2 with remainder 0

Therefore, the greatest common divisor is 12. As we can see, we must divide until the remainder is 0 and the last divisor will be the GCF.

• Based on the least common multiple : The numbers are multiplied and the result divided by their least common multiple (LCM).

We must remember that the least common multiple (LCM) is the smallest figure that satisfies the condition of being a multiple of all the elements of a set of numbers.

That is, going back to the same example, we can decompose as follows:

216 = (3 ^ 3) * (2 ^ 3) and 156 = 13 * 3 * (2 ^ 2) 204 = 3 * (2 ^ 2) * 17 168 = 3 * (2 ^ 3) * 7

The least common multiple would be: (3 ^ 3) * (2 ^ 3) * 13 * 17 * 7 = 334.152

So: GCD = 216 * 156 / 2.808 = 12

It is worth mentioning that this method works only for two numbers.

Numeric sets

• Maximum (math)
• Law of the big numbers
• Decimal numbers and fractions