Greatest Common Divisor

Dhristi JEE 2022-24

What is meant by Greatest Common Divisor?

In the field of mathematics, the term Greatest Common Divisor is defined as the largest possible positive integer which divides the given numbers and gives zero as the remainder. The Greatest common divisor is also known as the greatest common denominator, greatest common factor (GCF), or highest common factor (HCF). When we refer to the term "Greatest Common Divisor", the adjective "greatest" can easily be replaced by "highest", and the word "divisor" also can be replaced by "factor". Hence, we also know the greatest common divisor as the Highest Common Factor, Greatest Common Factor (GCF), etc.


Method to Calculate GCD and its Applications

As we have established, the GCD of any two or more such integers will be the largest integer that will divide each of the integers such that their remains will be zero. So, there are various methods or algorithms to determine the G.C.D (Greatest Common Divisor) between any two given numbers. So, if we talk about the easiest and fastest process to calculate the GCF, it would consist of decomposing every one of the numbers given in the form of products of prime factors, and then successively dividing each one of the numbers by the prime numbers until we reach a quotient that equals 1. For example, the GCD of 20 and 30 = 10 (as 10 is the highest common number that divides 20 and 30 with the remainder as zero).


The GCD of 42, 120, and 285 = 3 (as 3 is the highest common number that divides 42, 120, and 285 with the 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, it comprises decomposing each of the numbers in the products of prime factors, and then successively dividing each one of the numbers by the prime numbers until we reach a quotient that equals 1. 


We are going to discuss an example to make it 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 making factors, we shall arrive at the conclusion that 168 = 2 × 2 × 2 × 3 × 7 and 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 that 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), having the same amount of flowers. In this situation, by determining 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, where each one will have 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? To solve fractions with different denominators, 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 an eight. For 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 there because that divisor corresponds to the number 1, these are called relatively primary numbers. But if they have various common divisors, then the G.C.D will be the greatest of those divisors.

FAQs on Greatest Common Divisor

1. What are GCD and LCM?

The least common multiple (LCM) of any two numbers is the smallest positive integer, which is a multiple of both, but the greatest common divisor (GCD) of any two numbers is the greatest positive number that divides both. So, the product of the two numbers will be the product of the LCM and the GCD. This is a very important fundamental concept of mathematics that is extremely useful during higher studies.

2. What is a natural number?

In mathematics, those numbers that are used for counting or ordering are known as natural numbers. In common mathematical terminology, the words that are colloquially used for counting are cardinal numbers and words that are used for ordering are ordinal numbers. So, the natural numbers can, at times, appear as a convenient set of codes, that is, as what linguists usually say are nominal numbers.

3. How can I score good marks on the topic of HCF?

The GCD, or the HCF, as it is sometimes called, is one of the basic concepts of mathematics, and it is extremely important for higher-level mathematics. Students must have a good grasp on the fundamentals of this subject and understand the basics. The students must be attentive in class, any doubts which may arise in the minds of students must be clarified with the teachers, and all the exercise questions must be solved. We provide high-quality study materials and solved exercises that will help the students in understanding this subject.

Comment