Question

Using Euclid's algorithm, find the HCF of $405$ and $2520$

Answer 1

Solution:

Step 1: Stating Euclid's algorithm:

Given numbers are $405$ and $2520$

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=2520andb=405$

$\Rightarrow 2520=(405\times 6)+90$

Step 3: Use Euclid's algorithm for $a=405andb=90$

$\Rightarrow 405=(90\times 4)+45$

Step 4: Use Euclid's algorithm for $a=90andb=45$

$\Rightarrow 90=(45\times 2)+0$

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