Question

Express HCF of 305 and 793 as 305x + 793y where x and y are integers.

Answer 1

According to Euclid's division lemma
a=bq+r 0<r<=b
793=305×2+183
305=183×1+122
183=122×1+61
122=61×2+0


61=183-122×1
61=183-[305-183×1]×1
61=183-305+183×1
61=183×2-305
61=[793-305×2]×2-305
61=793×2-305×4-305
61=793×2-305×5
61=793x+305y

x=2, y=(-5)

Answer 2

Euclid division lemma :-
a=bq+r
793=305(2)+183
305=183(1)+122
183=122(1)+61
122=61(2)+0
As the remainder is 0,hcf of 793 and 305 is 61.

61=183-122×1
61=183-[305-183×1]×1
61=183-305+183×1
61=183×2-305×1
61=[793-305×2]×2-305
61=793×2-305×4-305
61=793×2-305×5
61=-305×5+793×2
61=305(-5)+793(2)
61=305x+793y
where x=-5 and y=2

Hope it helps