Q. 45.0( 1 Vote )

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

Answer :

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 GeometryKnow About Euclids GeometryKnow About Euclids Geometry46 mins
Euclid's Fifth Postulate and its ApplicationsEuclid's Fifth Postulate and its ApplicationsEuclid's Fifth Postulate and its Applications36 mins
Doubt Session  - Introduction to Euclid's GeometryDoubt Session  - Introduction to Euclid's GeometryDoubt Session - Introduction to Euclid's Geometry32 mins
Euclid's GeometryEuclid's GeometryEuclid's Geometry51 mins
Euclid's Most Interesting Postulate.Euclid's Most Interesting Postulate.Euclid's Most Interesting Postulate.42 mins
Quiz | Imp. Qs. on Coordinate GeometryQuiz | Imp. Qs. on Coordinate GeometryQuiz | Imp. Qs. on Coordinate Geometry39 mins
Know How to Solve Complex Geometry Problems!Know How to Solve Complex Geometry Problems!Know How to Solve Complex Geometry Problems!27 mins
Coordinate GeometryCoordinate GeometryCoordinate Geometry45 mins
Introduction to HeatIntroduction to HeatIntroduction to Heat45 mins
Basics of Coordinate GeometryBasics of Coordinate GeometryBasics 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
caricature
view all courses
RELATED QUESTIONS :