Question

Using Euclid's division algorithum find the hcf of 636 and 36

Answer 1

Euclid's division lemma :

Let a and b be any two positive Integers .

Then there exist two unique whole numbers q and r such that

a = bq + r ,

0 ≤ r <b

Now ,

Clearly, 636 > 36

Start with a larger integer , that is 636.

Applying the Euclid's division lemma to 636 and 36, we get

636 = 36 x 17 + 24

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

36 = 24 × 1 + 12

We consider the new divisor 24 and remainder 12 and apply the division lemma to get

24 = 12 × 2 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 12 is the HCF of 636 and 36.

Answer 2

$\huge{\mathcal{\purple{A}\green{N}\pink{S}\blue{W}\purple{E}\green{R}\pink{!}}}$

➦Since 636 > 36 ,we apply the division lemma to 636 and 36 to get

➭ 636= 36 × 17 + 24

Since the reminder 24 ≠ 0,we apply the division lemma to 36 and and 24 ,to get

➭ 36 = 24 × 1 +12

we consider the new divisor 24 and the new remainder 12 and apply the division lemma to get

➭ 24 = 12 × 2 + 0

Here, the remainder become zero so our procedure stops. Since the divisor at this stage is 12 .

∴The HCF of 636 and 36 is 12 .