Question

Using Euclid Division 'LEMMA' , find which of the following pairs of numbers are co-primes :-
1) 231,396
2) 847,2160​

Answer 1

1) 396 , 231396=231 x 1 + 165

231=165 x 1 + 67

165=67 x 2 + 31

67=31 x 2 + 5

31=5 x 6 +1

5=1 x 5 + 0

2) 2160,8472160=847 x 2 +366

847=366 x 2 +115

366=115 x 2 +36

115=36 x 3 + 7

36=7 x 5 + 1

5=1 x 5 + 1

∴ these both are co-primes