Question

If the HCF of 657 and 963 is expressible in the form 657x + 963y − 15, find x.

Answer 1

By applying Euclid’s division lemma

963 = 657 × 1 + 306

Since remainder ≠ 0, apply division lemma on division 657 and remainder 306

657 = 306 × 2 + 45

Since remainder ≠ 0, apply division lemma on division 306 and remainder 45

306 = 45 × 6 + 36

Since remainder ≠ 0, apply division lemma on division 45 and remainder 36

45 = 36 × 1 + 19

Since remainder ≠ 0, apply division lemma on division 36 and remainder 19

36 = 19 × 4 + 0

∴ HCF = 657

Given HCF = 657 + 963 × (-15)

⇒ 9 = 657 × −1445

⇒ 9 + 14445 = 657 x

⇒ 657x = 14454

⇒ x =`(14454)/657`

⇒ x = 22