Greatest Common Divisor

GCD

A largest number that exactly divides two or more integers.

In general, Greatest Common Divisor (GCD) is otherwise called as Greatest Common Factor (GCF) or Highest Common Factor (HCF)

How to Find GCD

There are more than one way to find the GCD of two or more integers. But here we will see one of the easiest method which can be easily implemented in any programming language.

  1. Find the minimum value of the given integers
  2. Always go with the multiples of 1 upto the minimum value (which you find in step 1).
  3. Now, find the greater common divisor which can exactly divide all the given integers.

2 and 3

In this example, we will find the greatest common divisor of 2 and 3. Here, the mininum value is 2

2 = 1, 2

3 = 1, 2

Note: No other number greater than 1 will exactly divide both 2 and 3.

Clearly, 1 is the largest number that can exactly divide both 2 and 3.

5 and 10

In this example, we will find the greatest common divisor of 5 and 10. Here, the mininum value is 5

5 = 1, 2, 3, 4, 5

10 = 1, 2, 3, 4, 5

Note: No other number greater than 5 will exactly divide both 5 and 10.

Clearly, 5 is the largest number that can exactly divide both 5 and 10.

36 and 60

In this example, we will find the least common multiple of 36 and 60. Here, the mininum value is 36

36 = 1, 2, 3, ..., 11, 12, 13, ..., 36

60 = 1, 2, 3, ..., 11, 12, 13, ..., 36

Note: No other number greater than 12 will exactly divide both 36 and 60.

Clearly, 12 is the largest number that can exactly divide both 36 and 60.

Examples

The following table provides few examples of GCD of the given numbers.

NumbersGCD
4, 10 2
6, 5 1
15, 30 , 45 15

Calculator

The following calculator will help you to find GCD of any given numbers.

Useful links

Share this Page

Meet the Author