Find the HCF of numbers 134791, 6341, 6339 by Euclid's division algorithm.

We know Euclid's division lemma:

Let a and b be any two positive integers. Then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.

According to the problem given,

Start with 6341 and 6339.

Apply the division lemma,

6341 = (6339 × 1) + 2

Since the remainder is not equal to zero, apply lemma again on 6339 and 2.

6339 = (2 × 3169) + 1

Since the remainder is not equal to zero, apply lemma again on 2 and

1.

2 = (1 × 2) + 0

The remainder has now become zero.

⇒ HCF (6341, 6339) = 1

Now we have to find HCF of 1 and 134791.

Similarly, apply lemma on 134791 and 1.

134791 = (1 × 134791) + 0

⇒ HCF (1, 134791) = 1

Therefore, HCF (134791, 6341, 6339) = 1