Q. 45.0( 1 Vote )

# 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.

Rate this question :

How useful is this solution?
We strive to provide quality solutions. Please rate us to serve you better.
Related Videos  Know About Euclids Geometry46 mins  Euclid's Fifth Postulate and its Applications36 mins  Doubt Session - Introduction to Euclid's Geometry32 mins  Euclid's Geometry51 mins  Euclid's Most Interesting Postulate.42 mins  Quiz | Imp. Qs. on Coordinate Geometry39 mins  Know How to Solve Complex Geometry Problems!27 mins  Coordinate Geometry45 mins  Introduction to Heat45 mins  Basics of Coordinate Geometry43 mins
Try our Mini CourseMaster Important Topics in 7 DaysLearn from IITians, NITians, Doctors & Academic Experts
Dedicated counsellor for each student
24X7 Doubt Resolution
Daily Report Card
Detailed Performance Evaluation view all courses RELATED QUESTIONS :