Use Euclid's algorithm to find the H.C.F. of 4052 and 12576.

Explanation

Euclid`'`s algorithm states that , for any two integers `a` and `b` such that `a > b`, if we can write,

`a = bq+r`, where `q` is quotient and `r` is remainder, then,

`HCF(a,b) = HCF(q,r)`

In our case, `a = 12576` and `b=4052`

`12576 = 4052**3+420`

So, `HCF(12576,4052) = HCF(4052,420)`

Similarly,

`4052 = 420**9+272`

...