Question

Find the HCF of 1260 and 7344 using Euclid's algorithm?

Answer 1

Step 1: Stating Euclid's algorithm

Given numbers are 1260 and 7344

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

Step 2: Use Euclid's algorithm for $a=7344\mathrm{and}b=1260$

$7344=\left(1260\times 5\right)+1044$

Step 2: Use Euclid's algorithm for $a=1260\mathrm{and}b=1044$

$1260=\left(1044\times 1\right)+216$

Step 4: Use Euclid's algorithm for $a=1044\mathrm{and}b=216$

$1044=\left(216\times 4\right)+180$

Step 5: Use Euclid's algorithm for $a=216\mathrm{and}b=180$

$216=\left(180\times 1\right)+36$

Step 6: Use Euclid's algorithm for $a=180\mathrm{and}b=36$

$180=\left(36\times 5\right)+0$

Final Answer:

Hence, by Euclid's algorithm the HCF of 1260 and 7344 is obtained as $\mathbf{36}$.