By applying Euclid’s division lemma on 1288 and 575, we get
1288 = 575 x 2+ 138………… (1)
As the remainder ≠ 0, apply division lemma on divisor 506 and remainder 143
575 = 138 x 4 + 23……………. (2)
As the remainder ≠ 0, apply division lemma on divisor 143 and remainder 77
138 = 23 x 6 + 0……………….. (3)
Thus, we can conclude the H.C.F. = 23.
Now, in order to express the found HCF as a linear combination of 1288 and 575, we perform
23 = 575 – 138 x 4 [from (2)]
= 575 – [1288 – 575 x 2] x 4 [from (1)]
= 575 – 1288 x 4 + 575 x 8
= 575 x 9 – 1288 x 4
