Greatest Common Divisor

Bookmark added to your notes.
View Notes
×

In mathematics, the greatest common divisor (gcd) is the largest possible positive integer which divides the numbers with zero remainder. Greatest common divisor is also known as which is also known as the greatest common denominator, greatest common factor (gcf), or highest common factor (hcf).

For example, the GCD of 14 and 63 will be 7.

In the name "greatest common divisor", the adjective "greatest" can easily be replaced by "highest", and the word "divisor" also can be replaced by "factor", so that’s why we also known greatest common divisor as Highest common factor also these are called as the greatest common factor (gcf), etc.

The GCD of two or more integers will be the largest integer which will divide each of the integers such that their remainder will be zero.

Example

GCD of 20 and 30 = 10  (As 10 is the highest common number which divides 20 and 30 with remainder as zero).

GCD of 42, 120 and 285 = 3  (3 is the highest common number which divides 42, 120 and 285 with remainder as zero).


How to Calculate the G.C.D?

There are various methods or algorithms to determine the G.C.D (Greatest Common Divisor) between two given numbers. If we talk about the easiest and fastest process so it consists in decomposing each one of the numbers in the products of prime factors, this is, and then we successively divide each one of the numbers by the prime numbers until we reach a quotient that equals 1. 

We are going to discuss with you an example so as to be easier for you to understand. We want to determine the G.C.D between 168 and 180. First of all We start by factoring each one of the numbers as shown below.


168

2

84

2

42

2

21

3

7

7

1



180

2

90

2

45

3

15

3

5

5

1



By doing Factors we shall arrive at the conclusion that 168 = 2 × 2 × 2 × 3 × 7 and that 180 = 2 × 2 × 3 × 3 × 5.

In the next step we shall determine the product of common factors with a smaller exponent: 2 × 2 × 3 = 12. 

Finally, we can conclude the Greatest Common Divisor between 168 and 180 will be equal 12.


Applications of Greatest Common Divisor

There are various problems in which the determination of the G.C.D is very useful. Let’s assume that a florist has 180 roses and 168 daisies and she wants to make the count of bunches in which she can have both types of flowers (roses and daisies)  and having the same amount of flowers. In this situation, by determinin that the G.C.D is 12 it is enough to do 168:12=14 and 180:12=15. Thus, it is possible to make 12 bunches which will be having each one with 14 roses and 15 daisies.

Applications of LCM and GCD Definitely Help in Quite a Lot of Things.

Here are some of them:

  1. Helps in arithmetic for solving fractions. Doesn't it? Fractions with different denominators, to solve them we first bring them to have common denominators.

  2. Helps to find commonality. 2*4=8, 4*2=8 as well, we can use either 2 four times or 4 two times to bring a eight. Cases where you need to distribute, what if the same 10 chocolates were to be given to five kids instead of 2?

  3. We usually find use of GCD in measurements and construction fields.

  4. If we know the LCM and GCD, then we can simply find the product of numbers.

What is the G.C.D of Two Numbers?

First of all, we have already discussed that the G.C.D is not only calculated between two numbers. We can determine the G.C.D of 2, 3, 4 or more numbers as well Thus, Let us assume we have two different natural numbers Now we assure you that there will be common divisors among them. If there is a case in which only a common divisor is because that divisor corresponds to number 1 and in that situation these are called relatively primary numbers. But if they have various common divisors, so the G.C.D will be the greatest of those divisors.

FAQ (Frequently Asked Questions)

1. Is GCD and HCF the Same?

Ans: GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is nothing but the greatest number which divides both of them. 

For instance GCD of 28 and 20  is 4 and GCD of 56 and  98 is 14.

2. What is GCD and LCM?

Ans: The least common multiple (LCM) of two numbers is the smallest positive number which is a multiple of both while The greatest common divisor (GCD) of two numbers is the greatest positive number which divides both. The product of the two numbers will be the product of the LCM and the GCD.

3. What is the Greatest Common Divisor of 24 and 36?

Ans: The GCF or GCD of 36  and 24 is 12. 'GCF' means 'greatest common factor'.

4. What is LCM and GCD with Examples?

Ans: Greatest Common Factor (GCF)

A common factor is a number that is a multiple of two or more common numbers.Usually  Common multiples of 2 and 3 are 0, 6, 12, 18, ...From this list The least common multiple (LCM) of two numbers is the smallest number (excluding zero) which is a multiple of the numbers.


5. What is the GCF of 36 and 54?

Ans: First of all find the common factors of both 36 and 54, 18 will be the greatest common factor. The second method to determine the greatest common factor is to list the prime factors, then multiply those common prime factors.


6. What is the Greatest Common Factor of 18 and 27 ?

Ans: The factors of 27 are 1, 3, 9, 27 and the factors of 18 are 1, 2, 9. 

Now The common factors of 18 and 27 are 1 and 9 then  The greatest common factor or GCD of 18 and 27 will be 9.