Question

Use Euclid's division algorithm to find the HCF of $726$ and $275$.

Answer 1

Using Euclid's division algorithm:

According to Euclid’s division lemma if we have two positive integers $a$ and $b$, then there exist unique integers $q$ and$r$ which satisfies the condition

$a=bq+rwhere0\le r<b$

Consider two numbers $726$ and $275$, and we need to find the HCF of these numbers.

When the reminder is zero then the quotient is the HCF.

$$\begin{gathered} 726=275x2+176 \\ 275=176x1+99 \\ 176=99x1+77 \\ 99=77x1+22 \\ 77=22x3+11 \\ 22=11x2+0 \end{gathered}$$

Therefore, the HCF of $726$ and $275$ is $11$.