Express the hcf of 963 and …

By applying Euclid’s division lemma,
{tex}963 = 657\times  1 + 306.{/tex}
Since remainder ≠ 0, apply division lemma on divisor 657 and remainder 306
{tex}657 = 306\times  2 + 45.{/tex}
Since remainder ≠ 0, apply division lemma on divisor 306 and remainder 45
{tex}306 = 45\times  6 + 36.{/tex}
Since remainder ≠ 0, apply division lemma on divisor 45 and remainder 36
{tex}45 = 36\times  1 + 9.{/tex}
Since remainder ≠ 0, apply division lemma on divisor 36 and remainder 9
{tex}36 = 9 \times 4 + 0.{/tex}
Therefore, {tex}H.C.F. = 9.{/tex}

HCF of 2 numbers can be expressed as the linear combination of the numbers
{tex}\Rightarrow {/tex} 9 = 45 - 36 {tex}\times{/tex} 1
= {tex}45 - [306 - 45 \times 6] \times 1 = 45 - 306\times  1 + 45\times  6{/tex}
= {tex}45 \times 7 - 306\times  1 = [657 -306\times  2]\times  7 - 306 × 1{/tex}
= {tex}657 \times 7 - 306 \times 14 - 306 × 1{/tex}
= {tex}657\times  7 - 306\times  15{/tex}
= {tex}657\times  7 - [963 - 657 × 1] \times 15{/tex}
= 657 {tex}\times{/tex} 7 - 963 {tex}\times{/tex} 15 + 657 {tex}\times{/tex} 15
= 657 {tex}\times{/tex} 22 - 963 {tex}\times{/tex} 15.
Hence, obtained.