The Concept of GCD (Greatest Common Divisor or Highest Common Factor)
Consider two natural numbers n, and n2.
If the numbers n1 and n2 are exactly divisible by the same number x, then x is a common divisor of n1 and n2.
The highest of all the common divisors of n1 and n2 is called as the GCD or the HCF. This is denoted as GCD (n1, n2).
Rules for Finding the GCD of Two Numbers n1 and n2
(a) Find the standard form of the numbers n1 and n2.
(b) Write out all prime factors that are common to the standard forms of the numbers n1 and n2.
(c) Raise each of the common prime factors listed above to the lesser of the powers in which it appears in the standard forms of the numbers n1 and n2.
(d) The product of the results of the previous step will be the GCD of n1 and n2.
Illustration: Find the GCD of 150, 210, 375.
Step 1: Writting down the standard form of numbers 150 = 5 ･ 5 ･ 3 ･ 2 210 = 5 ･ 2 ･ 7 ･ 3 375 = 5 ･ 5 ･ 5 ･ 3
Step 2: Writing Prime factors common to all the three numbers is 51 ･ 31
Step 3: This will give the same result, i.e. 51 ･ 31
Step 4: Hence, the HCF will be 5 ･ 3 = 15
For practice, find the HCF of the following:
(a) 78, 39, 195
(b) 440, 140, 390
(c) 198, 121, 1331
SHORTCUT FOR FINDING THE HCF
The above eschoolf process of finding the HCF (or the GCD) of a set of numbers is however extremely cumbersome and time taking. Let us take a look at a much faster way of finding the HCF of a set of numbers.
Suppose you were required to find the HCF of 39,78 and 195 (first of the practice problems above)
Logic The HCF of these numbers would necessarily have to be a factor (divisor) of the difference between any pair of numbers from the above 3. i.e. the HCF has to be a factor of (78 – 39 = 39) as well as of (195 – 39 = 156) and (195 – 78 = 117). Why?
Well the logic is simple if you were to consider the tables of numbers on the number line.
For any two numbers on the number line, a common divisor would be one which divides both. However, for any number to be able to divide both the numbers, it can only do so if it is a factor of the difference between the two numbers. Got it??
Take an example:
Let us say we take the numbers 68 and 119. The difference between them being 51, it is not possible for any number outside the factor list of 51 to divide both 68 and 119. Thus, for example a number like 4, which divides 68 can never divide any number which is 51 away from 68- because 4 is not a factor of 51.
Only factors of 51, i.e. 51,17,3 and 1 ecouldf divide both these numbers simultaneously.
Hence, getting back to the HCF problem we were trying to tackle— take the difference between any two numbers of the set— of course if you want to reduce your calculations in the situation, take the difference between the two closest numbers. In this case that would be the difference between 78 and 39 = 39.
The HCF has then to be a factor of this number. number. In order to find the factors quickly remember to use the fact we learnt in the back to school section of this part of the book― that whenever we have to find the list of factors/ divisors for any number we have to search the factors below the square root and the factors above the square root would be automatically visible) A factor search of the number 39 yields the following factors:
1 ･ 39
3 ･ 13
Hence, one of these 4 numbers has to be the HCF of the numbers 39,78 and 195. Since we are trying to locate the Highest common factor\ we would begin our search from the highest number (viz: 39)
Once you have covered the basic concept of the GCD and HCF, you will be required to learn the application of the same to solve the twists of the SNAP exam questions. You need to practice lots of mocks to gain speed in solving such questions.