Question

Use Euclid's Division Algorithm to find HCF of:

$126$ and $1078$

Answer 1

Find HCF of $1078$ and $126$:

HCF means the highest common factors of two or more numbers.

Euclid's division algorithm: For any given positive integers$aandb$, there exist unique integers $q$ and $r$ satisfying $a=bq+r,0\le r<b$

Since $1078>126$ we have to apply Euclid's Division Algorithm

$1078=126\times 8+70$

Since remainder $70$≠$0$, so we again apply Euclid's Division Algorithm

$126=70\times 1+56$

Since remainder $56$≠$0$, so we again apply Euclid's Division Algorithm

$70=56\times 1+14$

Since remainder $14$≠$0$, so we again apply Euclid's Division Algorithm

$56=14\times 4+0$

Since the remainder is zero, the process will be stopped.

Since the divisor at this stage is $14$

Hence, the HCF of $(1078,126)=14$.