Question

Using Euclid's division algorithm find the HCF of the following numbers.
$8262$ and $101592$

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\le r<b$

Now ,starting with the largest integer , that is $101592$,

Apply the division lemma to $101592$ and $8262$,

$101592=8262\times 12+2448$

$8262=2448\times 3+918$

$2448=918\times 2+612$

$918=612\times 1+306$

$612=306\times 2+0$

The remainder has now become zero , so our procedure stops.

Since the divisor at this stage is $306$ .

$\therefore HCF(101592,8262)=306$