# How to Find Greatest Common Divisor (GCD or HCF)

Here you will learn concept of gcd ot hcf and how to find greatest common divisor or highest common factor of numbers and fractions with examples.

Let’s begin –

## Concept of GCD or HCF

Consider two natural numbers $$n_1$$ and $$n_2$$.

If the numbers $$n_1$$ and $$n_2$$ are exactly divisible by the same number x, then x is a common divisor of $$n_1$$ and $$n_2$$.

The highest of all the common divisors of $$n_1$$ and $$n_2$$ is called as the GCD or HCF. This is denoted as GCD($$n_1$$, $$n_2$$)

## How to Find Greatest Common Divisor (GCD)

(a) Find the standard form of the numbers.

(b) Write out all the prime factors that are common to the standard form of the numbers.

(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.

(d) The product of the results of the previous step will be the GCD of the numbers.

## Rule for finding HCF of Fractions

HCF of two or more fractions is given by:

$$HCF of Numerators\over LCM of Denominators$$

Example : Find the GCD of 150, 210, 375.

Solution : We have the numbers, 150, 210, 375.

1). Writing down the standard form of numbers.

150 = $$5 \times 5 \times 3 \times 2$$

210 = $$5 \times 2 \times 7 \times 3$$

375 = $$5 \times 5 \times 5 \times 3$$

2). Writing Prime factors common to all the three numbers is $$5^1 \times 3^1$$.

3). This will give the same result, i.e. $$5^1 \times 3^1$$

4). Hence, the HCF or GCD will be $$5\times 3$$ = 15

Example : Find the GCD of 50, 75.

Solution : We have the numbers, 50, 75

1). Writing down the standard form of numbers.

50 = $$5 \times 5 \times 2$$

75 = $$5 \times 5 \times 3$$

2). Writing Prime factors common to all the two numbers is $$5^1 \times 5^1$$.

3). This will give the same result, i.e. $$5^1 \times 5^1$$

4). Hence, the HCF or GCD will be $$5\times 5$$ = 25

## Some Other Rules for HCF

If the HCF of x and y is G, then the HCF of

(i) x, (x + y) is also G

(ii) x, (x – y) is also G

(iii) (x + y), (x – y) is also G