Highest Common Factor

Q. Find the Highest Common Factor of 36 and 84

• The greatest number among all the common factors of two or more numbers is known as HCF (Highest Common Factor)

• The methods to find the HCF of 36 and 84 are given below:

1. 1. Long Division Method
   2. Prime Factorization Method
   3. Using Euclid’s Algorithm

• Finding HCF of 36 and 84 by using the long division method

1. 1. Firstly, Divide 84 (larger number) by 36 (smaller number).
   2. Secondly, Since the remainder ≠ 0, we will divide the divisor of step 1 (36) by the remainder (12).
   3. Thirdly, Repeat the above-mentioned process until the remainder = 0.
   4. The corresponding divisor (12) is the HCF of 36 and 84.

• Finding HCF of 36 and 84 by using Prime Factorization Method

1. 1. Prime factorization of 36 = (2 × 2 × 3 × 3) and 84= (2 × 2 × 3 × 7) 
   2. common prime factors of 36 and 84 are 2, 2, and 3. 
   3. Hence, the HCF of 36 and 84 is 2 × 2 × 3 = 12.

• Finding HCF of 36 and 84 by using Euclid’s Algorithm

According to Euclidean Algorithm, HCF (X, Y) = HCF (Y, X mod Y)

where X > Y and the mod is the modulo operator.

Here, X = 84 and Y = 36

• • HCF (84, 36) = HCF (36, 84 mod 36) = HCF (36, 12)
  • HCF (36, 12) = HCF (12, 36 mod 12) = HCF (12, 0)
  • HCF (12, 0) = 12 (∵ HCF (X, 0) = |X|, where X ≠ 0)

Therefore, the value of HCF of 36 and 84 is 12.