Question

Use Euclid's algorithm to find the HCF of 4052 and 12576. [3 MARKS]

Answer 1

Concept : 1 Mark
Calculation : 2 Mark

Using Euclid's algorithm,

$a=bq+r,where0\le r<b$

Clearly, $12576>4052[a=12576,b=4052]$

$\Rightarrow 12576=4052\times 3+420$

$\Rightarrow 4052=420\times 9+272$

$\Rightarrow 420=272\times 1+148$

$\Rightarrow 272=148\times 1+124$

$\Rightarrow 148=124\times 1+24$

$\Rightarrow 124=24\times 5+4$

$\Rightarrow 24=4\times 6+0$

The remainder at this stage is 0. So, the divisor at this stage, i.e., 4 is the HCF of 12576 and 4052