Question

Find the HCF of 55 and 210 by prime factorization and Express it as a linear combination of 55 and 210

Answer 1

HCF of 210 & 55

210 = 55 × 3 + 45 ….....(i)
55 = 45 × 1 +10 ….........(ii)
45 = 10 × 4 +5 …...........(iii)
10 = 5 × 2 + 0
Hence HCF of 210 & 55 = 5

now from (iii), we get
4 5 = 10 × 4 + 5
so
5 = 45 – 10 × 4
5 = 45 – (55 – 45) × 4
5 = 45 – 55 × 4 + 45 × 4
5 = 45 × 5 – 55 × 4
5 = (210 – 55 ×3) ×5 – 55×4
5 = 210×5 – 55×15 – 55×4
5 = 210×5 – 55×19
5 = 210 x + 55 y
where x = 5, y = –19