Question

Find hcf of 1190 and 1445 by euclid algorithm .express hcf in the form 1190m+1445n

Answer 1

Hi ,

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

Euclid's division algorithm :

Let a and b are two positive Integers .

Then there exist two unique whole numbers

q and r such that

a = bq + r ,

0 ≤ r < b

**************"********************

Now ,

applying the division lemma to 1445 and

1190 ,

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

since the remainder is not equal to zero ,

we apply the division lemma to 1190 and

255

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

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

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

The remainder has become zero , so

our procedure stops .

Since the divisor at this stage is 85 .

Therefore ,

HCF( 1445 , 1190 ) = 85.

Now ,

85 = 255 - 170 [ from ( 3 ) ]

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

[ from ( 1 ) and from ( 2 ) ]

= 1445 - 1190 - 1190 + 255 × 4

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

[ from ( 1 ) ]

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

= 5 × 1445 - 6 × 11 90

85 = 1445 ( 5 ) + ( - 6 ) 1190

compare this with ,

85 = 1190m + 1445n [ given ]

m = -6 ,

n = 5

I hope this helps you.

: )

Answer 2

Answer to the question:

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)