Use Euclid’s division algorithm to find if the following pair of numbers is coprime 121, 573.

Let us understand what we mean by co-primes.

Two integers a and b are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1.

That is, if greatest common divisor (gcd) = 1 OR highest common factor (HCF) = 1.

And, 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.

Take numbers 121 and 573,

Apply Euclid’s lemma on 573 and 121.

We get,

573 = (121 × 4) + 89

Since the remainder is not equal to 0.

Apply lemma again on 121 and 89.

We get,

121 = (89 × 1) + 32

Since the remainder is not equal to 0.

Apply lemma again on 89 and 32.

We get,

89 = (32 × 2) + 25

Since the remainder is not equal to 0.

Apply lemma again on 32 and 25.

We get,

32 = (25 × 1) + 7

Since the remainder is not equal to 0.

Apply lemma again on 25 and 7.

We get,

25 = (7 × 3) + 4

Since the remainder is not equal to 0.

Apply lemma again on 7 and 4.

We get,

7 = (4 × 1) + 3

Since the remainder is not equal to 0.

Apply lemma again on 4 and 3.

We get,

4 = (3 × 1) + 1

Since the remainder is not equal to 0.

Apply lemma again on 3 and 1.

We get,

3 = (1 × 3) + 0

The remainder is 0 now.

⇒ HCF (121, 573) = 1.

Thus, 121 and 573 are coprime.