Question

Express the hcf of 968 and 657 as a linear combination of them

Answer 1

i) 963 and 6567
By applying Euclid’s division lemma 963 = 657 × 1 + 306 …(i)
Since remainder ≠ 0, apply division lemma on divisor 657 and remainder 306
657 = 306 × 2 + 45 ….. (ii)
Since remainder ≠ 0, apply division lemma on divisor 306 and remainder 4
306 = 45 × 6 + 36 …..(iii)
Since remainder ≠ 0, apply division lemma on divisor 45 and remainder 36
45 = 36 × 1 + 9 …… (iv)
Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9
36 = 9 × 4 + 0

∴ HCF = 9
Now 9 = 45 – 36 × 1 [from (iv)]
= 45 – [306 – 45 × 6] × 1 [from (iii)]
= 45 – 306 × 1 + 45 × 6
= 45 × 7 – 306 × 1
= 657 × 7 – 306 × 14 – 306 × 1 [from (ii)]
= 657 × 7 – 306 × 15
= 657 × 7 – [963 – 657 × 1] × 15 [from (i)]
= 657 × 22 – 963 × 15