Question

Using Euclid's algorithm, find the HCF of$960$ and $1575$.

Answer 1

Solution:

Step 1: Stating Euclid's algorithm:

Given numbers are $960$ and $1575$.

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: Express $1575$ and $960$ in the form $a=bq+r$

$1575=960\times 1+615$

Now we have to take $960$ as $a$ and $615$ as $b$

Step 3: Express $960$ and $615$ in the form $a=bq+r$

$960=615\times 1+345$

Now we have to take $615$ as $a$ and $345$ as $b$

Step 4: Express $615$ and $345$ in the form $a=bq+r$

$615=345\times 1+270$

Now we have to take $345$ as $a$ and $270$ as $b$

Step 5: Express $345$ and $270$ in the form $a=bq+r$

$345=270\times 1+75$

Now we have to take $270$ as $a$ and $75$ as $b$

Step 6: Express $270$ and $75$ in the form $a=bq+r$

$270=75\times 3+45$

Now we have to take $75$ as $a$ and $45$ as $b$

Step 6: Express $75$ and $45$ in the form $a=bq+r$

$75=45\times 1+30$

Now we have to take $45$ as $a$ and $30$ as $b$

Step 7: Express $45$ and $30$ in the form $a=bq+r$

$45=30\times 1+15$

Now we have to take $30$ as $a$ and $15$ as $b$

Step 8: Express $30$ and $15$ in the form $a=bq+r$

$30=15\times 2+0$

Now, the remainder is zero and the last divisor is $15$.

Final answer: Hence, the HCF of $960$ and $1575$ is$\mathbf{15}$.