Q. 45.0( 1 Vote )

Use Euclid’

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

In the given figuRS Aggarwal & V Aggarwal - Mathematics