. Here, 55 210 < . So, on applying Euclid’s division lemma to 210 and 55, we get 210 55 3 45 = × + ( ) …(i) (1/2) Here, remainder, 45 ≠ 0. So, we have to apply the division lemma to new dividend 55 and new divisor 45, we get 55 45 1 10 = × + ( ) …(ii) (1/2) Here, remainder, 10 ≠ 0. So, we have to apply the division lemma to new dividend 45 and new divisor 10, we get 45 10 4 5 = × + ( ) …(iii) (1/2) Here, remainder, 5 ≠ 0. So, again applying the division lemma to new dividend 10 and new divisor 5, we get 10 5 2 0 = × + Here, remainder = 0 (1/2) Thus, HCF of 210 55 and = Last divisor = 5 Now, to express the HCF as a linear combination of the two given numbers, start with Eq. (iii) and successively eliminates the previous remainders. From Eq. (iii), 5 45 10 4 = − × ( ) (1/2) ⇒ 5 45 55 45 1 4 = − − × × [( ) ] [from Eq. (ii), 55 45 1 10 − × = ( ) ] ⇒ 5 45 55 4 45 4 = − × + × ⇒ 5 5 45 55 4 = × − × [from Eq. (i), 210 55 3 45 − × = ( ) ] ⇒ 5 5 210 55 3 55 4 = × − × − × ( ) ⇒ 5 210 5 55 19 = × − × ⇒ 5 210 55 = + a b where, a = 5 and b = − 19
