Question

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

Answer 1

1445 = 1190*1 + 255

1190 = 255*4 + 170

255 = 170*1 + 85

170 = 85*2 + 0

So, now the remainder is 0, then HCF is 85

Now,

85 = 255 - 170

(1445 - 1190) - (1190 - 255*4)

⇒ 1445 - 1190 - 1190 + 255*4

⇒ 1445 - 1190*2 + (1445 - 1190)*4

⇒ 1445 - 1190*2 + 1445*4 - 1190*4

⇒ 1445*5 - 1190*6

⇒ 1190*(- 6) + 1445*5

1190m + 1445n , where m = - 6 and n = 5




Alternate solution



We know that Euclid's division Lemma is x and y for any two positive integers, there exist unique integers q and r satisfactorily x = yq + r, where 0 ≤ r <y. In case r=0 then y will be the HCF.

1445=1190x1+255
1190=255x4+170
255=170x1+85
170=85x2+0

We have found r=0
Hence, HCF(1190,1445)=85

So, now
85 = 255 - 170
=(1445-1190)-(1190-1020)
=(1445-1190)-(1190-255x4)
=1445-1190-1190+255x4
=1445-2×1190+(1445-1190)x4
=1445-2×1190+1445x4-1190x4
=1445+1445×4-2×1190-1190×4
=1445x5-1190x6
=-1190×6+1445×5
=1190x(-6)+1445x5
=1190m+1445n
(where m=-6 and n=5)



More clearly



Euclid's division lemma :

Let a and b be any two positive Integers.

Then there exists two unique whole numbers

q and r such that

a = bq + r ,

0 ≤ r < b

Alternatively ,

dividend = divisor × quotient + remainder

*******************************************

Now start with the larger interger , that is

1445 , apply the division lemma

1445 = 1190 × 1 + 255 ----( 1 )

1190 = 255 × 4 + 170 -----( 2 )


255 = 170 × 1 + 85 --------( 3 )

170 = 85 × 2 + 0 -----------( 4 )

The remainder has now become zero . so ,

our procedure stops .

Since the divisor at this stage is 85, the

HCF ( 1190 , 1445 ) = 85

Now ,
____

85 = 255 - 170 [ from ( 1 ) ]

= [ 1445 - 1190 × 1 ] - [ 1190 - 255 × 4 ]

[ from ( 1 ) and ( 2 ) ]

= 1445 - 1190 - 1190 + 255 × 4

= 1445 - 2 × 1190 + ( 1445 - 1190 × 1 ) × 4

[ from ( 1 ) ]

= 1445 - 2 × 1190 + 4 × 1445 - 4 × 1190

= 1190 ( - 6 ) + 1445 ( 5 )

compare with HCF = 1190m + 1445n

we easily conclude that ,

m = - 6 ;

n = 5 :

I hope this helps you.