Using Euclid’s division algorithm, find the HCF of

156 and 504

Given numbers are 156 and 504

Here, 504 > 156

So, we divide 504 by 156

By using Euclid’s division lemma, we get

504 = 156 × 3 + 36

Here, r = 36 ≠ 0.

On taking 156 as dividend and 36 as the divisor and we apply Euclid’s division lemma, we get

156 = 36 × 4 + 12

Here, r = 12 ≠ 0

So, on taking 36 as dividend and 12 as the divisor and again we apply Euclid’s division lemma, we get

36 = 12 × 3 + 0

The remainder has now become 0, so our procedure stops. Since the divisor at this last stage is 12, the HCF of 156 and 504 is 12.