Question

Using Euclid's Division lemma, find the HCF of 15 and 575.

Answer 1

Hint: Finding HCF using Euclid's division lemma is an algorithmic process. We start by setting the two variables p and q equal to the given numbers, with q being equal to the smaller one. Then we repeat the following process:
Apply Euclid's division lemma to the numbers p and q
i.e. p = aq+r where $0\le r\le q-1$
if r = 0 then stop the process and we have HCF = q
Otherwise set p = q and q =r and repeat the process.

Complete step-by-step answer:

We set p =575 and q = 15.
Now we apply Euclid's division lemma on p and q, we get
$575=15\times 38+5$
Here r = 5 .
So we set p = 15 and q =5 and repeat the process
Applying Euclid's division lemma on p and q, we get
$15=5\times 3+0$
Since r = 0, we stop the process and we have HCF = q =5.
Hence HCF (15,575)=5.

Note: Verification
We find the prime factorization of 15 and 575
We have $15={{3}^{1}}\times {{5}^{1}}$
Also, $575={{5}^{2}}\times {{23}^{1}}$
We know that if the prime factorization of a is $p_{1}^{{{\alpha }_{1}}}\times p_{2}^{{{\alpha }_{2}}}\times \cdots \times p_{n}^{{{\alpha }_{n}}}$ and the prime factorization of b is $p_{1}^{{{\beta }_{1}}}\times p_{2}^{{{\beta }_{2}}}\times \cdots \times p_{n}^{{{\beta }_{n}}}$ then the HCF of a and b is given by $p_{1}^{\min \left( {{\alpha }_{1}},{{\beta }_{1}} \right)}\times p_{2}^{\min \left( {{\alpha }_{2}},{{\beta }_{2}} \right)}\times \cdots \times p_{n}^{\min \left( {{\alpha }_{n}},{{\beta }_{n}} \right)}$.
Using the above property, we have
HCF of 15 and 575 $={{5}^{1}}=5$
Hence our answer is verified to be correct.