Using Euclid’s division algorithm, find whether the HCF of 847 and 2160 is co-prime or not?

According to Euclid’s Division Lemma, if a and b are 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.

So, apply the lemma on 2160 and 847.

We get,

2160 = (847 × 2) + 466

Since the remainder is not zero.

Apply the lemma again on 847 and 466.

We get,

847 = (466 × 1) + 381

Since the remainder is not zero.

Apply the lemma again on 466 and 381.

We get,

466 = (381 × 1) + 85

Since the remainder is not zero.

Apply the lemma again on 381 and 85.

We get,

381 = (85 × 4) + 41

Since the remainder is not zero.

Apply the lemma again on 85 and 41.

We get,

85 = (41 × 2) + 3

Since the remainder is not zero.

Apply the lemma again on 41 and 3.

We get,

41 = (3 × 13) + 2

Since the remainder is not zero.

Apply the lemma again on 3 and 2.

We get,

3 = (2 × 1) + 1

Since the remainder is not zero.

Apply the lemma again on 2 and 1

We get,

2 = (1 × 2) + 0

We have finally got remainder as 0.

⇒ HCF (847, 2160) = 1

If the HCF of 847 and 2160 is 1, then the numbers are co-primes.