Introduction - Greatest Common Divisor (GCD)

Are Mona and Oliver dating?

Mona likes Oliver. And Oliver likes Mona. Let's see if they are compatible ...

Mona:

  • likes listening to music
  • likes to swim
  • likes horses
  • likes to eat pizza
  • plays on the piano

Oliver:

  • likes listening to music
  • likes to swim
  • likes dogs
  • likes to eat pizza
  • plays the drums

Mona and Oliver have in common:

  • likes listening to music
  • likes to swim
  • likes to eat pizza
What's the GCD of 12 and 980?

At the page prime factorization we have found the following disassemblies for the numbers 12 and 980:

  • 2 × 2 × 3 = 12
  • 2 × 2 × 5 × 7 × 7 = 980

Now, what is the Greatest Common Divisor (GCD) for these two numbers?

Proceed exactly the same as with Mona and Oliver - search the commonalities: In both numbers we have 2 × 2.

Therefore, the Greatest Common Divisor (GCD) of 12 and 980 is 4.

Importance of the Greatest Common Divisor (GCD)

It is worth to think briefly about the meaning of the term Greatest Common Divisor.

The GCD always refers to at least two numbers and represents a number by which all these numbers can be divided without remainder. That's why it's called "Common Divisor".

One more Common Divisor of 12 and 980 is 2.

However, it is not a question about any Common Divisor - we are looking for the greatest!

There is no greater Common Divisor of 12 and 980 than 4.

If you simplify a fraction with the GCD of its numerator and denominator, you can reduce it directly to a Lowest Terms Fraction.

Greatest Common Divisor - other terms

The Greatest Common Divisor (GCD) is also known as the Greatest Common Factor (GCF), Highest Common Factor (HCF), Greatest Common Measure (GCM) or Highest Common Divisor (HCD).

Calculation of GCD through prime factorization

Find the Greatest Common Divisor (GCD) of a set of numbers by:

  1. disassembling them into prime factors and
  2. multiplying all their common prime factors

You can use a table as a sub-calculation:

  • Insert the prime factors in the first row as headline
  • Insert for each number in a separate line how often the corresponding prime factor occurs in the disassembly; insert the number itself into the last column.
  • You obtain the prime factors of the Greatest Common Divisor (GCD) by writing the lowest number of each prime factor into the last row.
  • Finally calculate the Greatest Common Divisor (GCD) by multiplying its prime factors. Enter the result in the field at the bottom right.

Example: Calculation of GCD through prime factorization

Another example: Calculate the GCD of 297, 1386 and 396!

The disassembly of 297:
Try the factor 2 → 297 ÷ 2 = does not work
Try the factor 3 → 297 ÷ 3 = 99 → first prime factor: 3
Try the factor 3 → 99 ÷ 3 = 33 → second prime factor: 3
Try the factor 3 → 33 ÷ 3 = 11 → third prime factor: 3

11 is a prime number, therefore it can't be disassembled any further. The disassembly is as follows: 3 × 3 × 3 × 11 = 297

Written as a table it looks like this:


The disassembly of 1386:
Try the factor 2 → 1386 ÷ 2 = 693 → first prime factor: 2
Try the factor 2 → 693 ÷ 2 = does not work
Try the factor 3 → 693 ÷ 3 = 231 → second prime factor: 3
Try the factor 3 → 231 ÷ 3 = 77 → third prime factor: 3
Try the factor 3 → 77 ÷ 3 = does not work
Try the factor 5 → 77 ÷ 5 = does not work
Try the factor 7 → 77 ÷ 7 = 11 → fourth prime factor: 7

11 is a prime number, therefore it can't be disassembled any further. The disassembly is as follows: 2 × 3 × 3 × 7 × 11 = 1386

Add another row to the table, representing 1386:


The disassembly of 396:
Try the factor 2 → 396 ÷ 2 = 198 → first prime factor: 2
Try the factor 2 → 198 ÷ 2 = 99 → second prime factor: 2
Try the factor 2 → 99 ÷ 2 = does not work
Try the factor 3 → 99 ÷ 3 = 33 → third prime factor: 3
Try the factor 3 → 33 ÷ 3 = 11 → fourth prime factor: 3

11 is a prime number, therefore it can't be disassembled any further. The disassembly is as follows: 2 × 2 × 3 × 3 × 11 = 396

And another row representing 396:


In order to find the Greatest Common Divisor (GCD), we only have to identify and multiply the common prime factors of the 3 numbers.

The Greatest Common Divisor (GCD) of 297, 1386 und 396 is:
3 × 3 × 11 = 99.

Insert the lowest number (often 0) of each prime factor into the last row. Finally, calculate the GCD by multiplying its prime factors and insert the result in the field at the bottom right:


Let's continue with: "Least Common Multiple (LCM)"