Question

Use Euclid division algorithm to find if the following pair of number is co_prime:123,573​

Answer 1

Let a=573 and b=123

From Euclid's Division Lemma,

a=bq+r

»573=123×4+81

As r≠0,

»123=81×1+42

As r≠0,

»81=42×1+39

As r≠0,

42=39×1+2

As r≠0,

39=2×19+1

As r≠0,

2=1×1+1

As r≠0,

1=1×1+0

Implies,1 is the HCF of 573 and 123

Hence,573 and 123 are a pair of co primes