Question

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

Answer 1

Hint: According to Euclid’s algorithm we have to divide the larger number with the lower number and if the remainder is not 0 then the remainder becomes the divisor and the divisor becomes the dividend and this process continues till the remainder becomes 0, then the last divisor we will have will be the HCF of the given two numbers.

Complete Step by Step Solution:
Step 1: Divide 12576 by 4052
$$\begin{array}{l}REMAINDER=420\\ DIVISOR=4052\end{array}$$
Step 2: Divide 4052 by 420
$$\begin{array}{l}REMAINDER=272\\ DIVISOR=420\end{array}$$
Step 3: Divide 420 by 272
$$\begin{array}{l}REMAINDER=148\\ DIVISOR=272\end{array}$$
Step 4: Divide 272 by 148
$$\begin{array}{l}REMAINDER=124\\ DIVISOR=148\end{array}$$
Step 5: Divide 148 by 124
$$\begin{array}{l}REMAINDER=24\\ DIVISOR=124\end{array}$$
Step 6: Divide 124 by 24
$$\begin{array}{l}REMAINDER=4\\ DIVISOR=24\end{array}$$
Step 7: Divide 24 by 4
$$\begin{array}{l}REMAINDER=0\\ DIVISOR=4\end{array}$$
Atlast the remainder is 0 and when the remainder becomes 0 the divisor is 4.
Therefore the HCF of 4052 and 12576 is 4.

Note: Do note that quotient is not important in Euclid's algorithm as it is not used anywhere; Also beware of minor calculation mistakes as in this type of questions it takes a lot of time to find and correct it.