Question

Using Euclid’s division algorithm find the HCF: 273070 and 434330​

Answer 1

Given :

• 273070 and 434330

To find :

• The HCF of 273070 and 434330 by Euclid’s Division Algorithm = ?

Step-by-step explanation:

Clearly, 273070 > 434330

Applying the Euclid's division lemma to 273070 and 434330, we get

434330 = 273070 x 1+ 161260

Since the remainder 161260 ≠ 0, we apply the Euclid's division lemma to divisor 273070 and remainder 161260 to get

273070 = 161260 x 1 + 111810

We consider the new divisor 161260 and remainder 111810 and apply the division lemma to get

161260 = 111810 x 1 + 49450

We consider the new divisor 111810 and remainder 49450 and apply the division lemma to get

111810 = 49450 x 2 + 12910

We consider the new divisor 49450 and remainder 12910 and apply the division lemma to get

49450 = 12910 x 3 + 10720

We consider the new divisor 12910 and remainder 10720 and apply the division lemma to get

12910 = 10720 x 1 + 2190

We consider the new divisor 10720 and remainder 2190 and apply the division lemma to get

10720 = 2190 x 4 + 1960

We consider the new divisor 2190 and remainder 1960 and apply the division lemma to get

2190 = 1960 x 1 + 230

We consider the new divisor 1960 and remainder 230 and apply the division lemma to get

1960 = 230 x 8 + 120

We consider the new divisor 230 and remainder 120 and apply the division lemma to get

230 = 120 x 1 + 110

We consider the new divisor 120 and remainder 110 and apply the division lemma to get

120 = 110 x 1 + 10

We consider the new divisor 110 and remainder 10 and apply the division lemma to get

110 = 10 x 11+ 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 10 is the HCF of 273070 and 434330.