Question

Using Euclid's division algorithm find the HCF of the following numbers.
$2024$ and $1872$

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 ,

start with a larger integer , that is $2024$,

Apply the division lemma to $2024$ and $1872$,

$2014=1872\times 1+152$

$1872=152\times 12+48$

$152=48\times 1+8$

$48=8\times 6+0$

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

Since the divisor at this stage is $8$ .

$\therefore HCF(2024,1872)=8$