Question

Using Euclid's algorithm, find the HCF of $504\mathrm{and}1188$.

Answer 1

Solution:

Step 1: Stating Euclid's algorithm:

Given numbers are $504$ and $1188$.

Euclid's algorithm: For any two positive integers $a$ and $b$, there exist two unique integers $q$ and $r$ such that $a=bq+r$. Here, $0\le r<b$.

Step 2: Use Euclid's algorithm for $a=1188andb=504$

$\Rightarrow 1188=(504\times 2)+180$

Step 3: Use Euclid's algorithm for $a=504andb=180$

$\Rightarrow 504=(180\times 2)+144$

Step 4: Use Euclid's algorithm for $a=180andb=144$

$\Rightarrow 180=(144\times 1)+36$

Step 5: Use Euclid's algorithm for $a=144andb=36$

$\Rightarrow 144=(36\times 4)+0$

Final answer: Hence, by using Euclid's algorithm the HCF of $504$ and $1188$ is obtained as $\mathbf{36}$.