Question

find the h. c. f of the following by using the euclid algorithm of 96 and 27​

Answer 1

Here 96 is greater than 27

a = bq + r where 0 ≤ r < b

Step 1: Since 96 > 27, we apply the division lemma to 96 and 27, to get

96 = 27 x 3 + 15

Step 2: Since the reminder 27 ≠ 0, we apply division lemma to 15 and 27, to get

27 = 15 x 1 + 12

Step 3: We consider the new divisor 15 and the new remainder 12, and apply the division lemma to get

15 = 12 x 1 + 3

We consider the new divisor 12 and the new remainder 3, and apply the division lemma to get

12 = 3 x 4 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 3, the HCF of 96 and 27 is 3

Notice that 3 = HCF(12,3) = HCF(15,12) = HCF(27,15) = HCF(96,27) .

Therefore, HCF of 96,27 using Euclid's division lemma is 3.