Question

Find the HCF of the following by using Euclid algorithm.
$300$ and $550$.

Answer 1

Euclid algorithm $a=bq+r$
$a>b$ and $0⩽r<b$.
$300$ and $550$
The positive integers are $300$ and $550$, $550>300$
Apply Euclid's algorithm to $550$ and $300$,
$\therefore 550=(300\ast 1)+250$
The remainder is $250$.
Apply Euclid's algorithm to $300$ and $250$,
$\therefore 300=(250\ast 1)+50$
The remainder is $50$.
Apply Euclid's algorithm to $250$ and $50$
$\therefore 250=(50\ast 5)+0$
The remainder is zero.
$\therefore$ HCF of $300$ and $550$ is $50$.