Question

Using Euclid division algorithm find H.C.F of $867$ and $255$.

Answer 1

According to Euclid’s Division Lemma if we have two positive integers $\mathrm{a}$ and $\mathrm{b}$, then there exist unique integers $\mathrm{q}$ and $\mathrm{r}$ which satisfies the condition

$\mathrm{a}=\mathrm{bq}+\mathrm{r}\mathrm{where}0\le \mathrm{r}<\mathrm{b}$

Highest Common Factor (H.C.F)

Highest Common Factor or H.C.F is the largest common divisor of two or more positive integers, as the mathematics rules dictate, appears to be the largest positive integer that divides the numbers without leaving a remainder.

Least common multiple(L.C.M)

In arithmetic, Least common multiple or L.C.M $(\mathrm{a},\mathrm{b})$ is the least common multiple of two numbers, $\mathrm{a}$ and $\mathrm{b}$. And the L.C.M is the smallest or least positive integer that is divisible by both $\mathrm{a}$ and $\mathrm{b}$.

Given numbers: $867$ and $255$.

Consider two numbers $867$ and $255$, and we need to find the H.C.F of these numbers.

$867$ is greater than $255$, so we will divide $867$ by $255$

$867=255\times 3+102$

Now lets divide $255$ by $102$

$\Rightarrow 255=102\times 2+51$

Now divide $102$ by $51$

$\Rightarrow 102=51\times 2+0$

Here reminder is zero.

∴ H.C.F of $(867,255)=51$.