Question

Using Euclid division algorithm, find which of the pairs of numbers are co-prime a)196 , 257

Answer 1

Note:

★ Two numbers a and b are said to be coprime ( relatively prime ) if their HCF is one , ie ; HCF(a,b) = 1 .

Solution :

Here,

We need to check whether the pair of given numbers ( 196 , 257 ) is coprime or not .

Thus,

Let's find the HCF of 196 and 257 using Euclid division algorithm .

196 ) 257 ( 1

- 196

61 ) 196 ( 3

- 183

13 ) 61 ( 4

- 52

9 ) 13 ( 1

- 9

4 ) 9 ( 2

- 8

1 ) 4 ( 4

- 4

×

Clearly,

The HCF of 196 and 247 is 1 .

Since,

HCF(196,247) = 1 , thus 196 and 247 are coprime.