Use Euclid's algorithm to find the HCF of 117 and 65 and then express

1.	Use Euclid's algorithm to find the HCF of 117 and 65 and then express it in the fom117 m +65 n where m and n are integers.
Answer» Euclid's Division Lemma :-a = bq +r 117 > 65 117 = 65 × 1 + 52 ----> [ 2 ] 65 = 52 x 1 + 13 -----> [1] 52 = 13 x 4 + 0 HCF = 13 13 = 65m + 117n From [ 1] ,13 = 65 - 52 x 1 From [2] ,52 = 117 - 65 x 1 ----> [3] Hence , 13 = 65 - [ 117 - 65 x 1 ] ------> from [3] = 65 x 2 - 117 = 65 x 2 + 117 x [-1 ] m = 2n = -1

Use Euclid's algorithm to find the HCF of 117 and 65 and then express it in the fom117 m +65 n where m and n are integers.

Answer»

Euclid's Division Lemma :-a = bq +r

117 > 65

117 = 65 × 1 + 52 ----> [ 2 ]

65 = 52 x 1 + 13 -----> [1]

52 = 13 x 4 + 0

HCF = 13

13 = 65m + 117n

From [ 1] ,13 = 65 - 52 x 1

From [2] ,52 = 117 - 65 x 1 ----> [3]

Hence ,

13 = 65 - [ 117 - 65 x 1 ] ------> from [3]

= 65 x 2 - 117

= 65 x 2 + 117 x [-1 ]

m = 2n = -1