Find the HCF of 408 and 96. Express it as a linear combination of . . .

Question : Find the HCF of 408 and 96. Express it as a linear combination of 96 and 408, i.e. HCF of 96 and 408 = 96x+408y, for some x, y, where x and y are not unique. 

Doubt by Gauri

Solution : 

HCF by Euclid's Division Lemma

408>96
408=96×4+24 — (1)
96  =24×4+0 
HCF = 24

Using equation (1)
24 = 408-96×4
24=408×96(-4)
24=96(-4)×408(1)

which is the required linear combination. 

where x=-4 and y=1