Question

Using Euclid’s algorithm, find the HCF of the following pairs of numbers.
I.280,12
II.288,120
II.867,254

Answer 1

Hint: According to Euclid’s theorem, there are infinitely many prime numbers. The largest number that divides all of the given numbers is called the Highest Common Factor (HCF) of the numbers. A simple way to find the highest common factor of two numbers is by expressing both the numbers as the product of all its prime factors and then finding the intersection of all factors present in both the numbers.

Complete step-by-step answer:
I.We have to find the HCF of 280,12; both of the numbers can be expressed as –
 $
  280 = 2 \times 2 \times 2 \times 5 \times 7 \\
  12 = 2 \times 2 \times 3 \;
  $
The prime factors that are common in the expansion of both the numbers are $ 2 \times 2 $
Thus, 4 is the highest common factor of 280 and 12.
So, the correct answer is “4”.

II.We have to find the HCF of 288,120; both of the numbers can be expressed as –
 $
  288 = 2 \times 2 \times 2 \times 2 \times 2 \times 3 \times 3 \\
  120 = 2 \times 2 \times 2 \times 3 \times 5 \;
  $
The prime factors that are common in the expansion of both the numbers are $ 2 \times 2 \times 2\times 3 $
Thus, the highest common factor of 288 and 120 is 24.
So, the correct answer is “24”.

III.We have to find the HCF of 867,254; both of the numbers can be expressed as –
 $
  867 = 3 \times 17 \times 17 \\
  254 = 2 \times 127 \;
  $
Both the numbers don’t have any prime number as a common factor, thus the highest common factor of 867 and 254 is 1.
So, the correct answer is “1”.

Note: Euclid’s division lemma states that for any two integers a and b, there exists unique integers q and r which satisfies the condition $ a = bq + r $ where $ 0 \leqslant r < b $ . To find the HCF of two positive integers, we use Euclid’s division lemma that means dividing those two positive integers by their highest common factor, the remainder is zero.