Question

Use Euclid’s algorithm to find the HCF of 1190 and 1445. Express the HCF in the form 1190m + 1445n.

Answer 1

Given: 1190 and 1445 find HCF and express it as 1190m + 1445n.

Step-wise calculation:

1. Apply Euclid’s algorithm (successive divisions):

1445 = 1190 × 1 + 255

1190 = 255 × 4 + 170

255 = 170 × 1 + 85

170 = 85 × 2 + 0

So, HCF = 85.

2. Express 85 as a linear combination by back-substitution:

From 255 = 1445 – 1190,

So, (1) 255 = 1445 – 1190.

From 170 = 1190 – 255 × 4, 

So, (2) 170 = 1190 – 4 × 255.

From 85 = 255 – 170, substitute (2) into this:

85 = 255 – (1190 – 4 × 255) 

= 255 – 1190 + 4 × 255 

= 5 × 255 – 1190.

Now substitute (1) for 255:

85 = 5 × (1445 – 1190) – 1190 

= 5 × 1445 – 5 × 1190 – 1190 

= 5 × 1445 – 6 × 1190

Thus, 85 = 1190 × (– 6) + 1445 × 5.

HCF(1190, 1445) = 85 and it can be written as 1190m + 1445n with m = – 6 and n = 5.