Question

Use Euclid’s algorithm to find the HCF of

4052

and

12576

.

Accepted Answer

Step 1 : Since $12576 > 4052$ , we apply the division lemma to $12576$ and $4052$ , to get
$12576 = 4052 \times 3 + 420$
Step 2 : Since the remainder $420 \neq 0$ , we apply the division lemma to $4052$ and $420$ , to get
$4052 = 420 \times 9 + 272$
Step 3 : We consider the new divisor $420$ and the new remainder $272$ , and apply the division lemma to get
$420 = 272 \times 1 + 148$
We consider the new divisor $272$ and the new remainder $148$ , and apply the division lemma to get
$272 = 148 \times 1 + 124$
We consider the new divisor $148$ and the new remainder $124$ , and apply the division lemma to get
$148 = 124 \times 1 + 24$
We consider the new divisor $124$ and the new remainder $24$ , and apply the division lemma to get
$124 = 24 \times 5 + 4$
We consider the new divisor $12576$ and the new remainder $4$ , and apply the division lemma to get
$24 = 4 \times 6 + 0$
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is $4$ , the HCF of $12576$ and $4052$ is $4$ .

Use Euclid’s algorithm to find the HCF of $4052$ and $12576$ .

Important Questions on Solved Examples

Learn and Prepare for any exam you want !

Use Euclid’s algorithm to find the HCF of 4052 and 12576.

Important Questions on Solved Examples

Learn and Prepare for any exam you want !

Use Euclid’s algorithm to find the HCF of $4052$ and $12576$ .