Use Euclid's algorithm to find half of 4052 and 12576.

Let us understand what we mean by co-primes.

Two integers a and b are said to be relatively prime, mutually prime, or coprime (also written co-prime) if the only positive integer (factor) that divides both of them is 1.

That is, if greatest common divisor (gcd) = 1 OR highest common factor (HCF) = 1.

And, we know Euclid's division lemma:

Let a and b be any two positive integers. Then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.

Take numbers 4052 and 12576.

Apply Euclid’s lemma on 12576 and 4052.

We get,

12576 = (4052 × 3) + 420

Since the remainder is not equal to 0.

Apply lemma again on 4052 and 420.

We get,

4052 = (420 × 9) + 270

Since the remainder is not equal to 0.

Apply lemma again on 420 and 270.

We get,

420 = (270 × 1) + 150

Since the remainder is not equal to 0.

Apply lemma again on 270 and 150.

We get,

270 = (150 × 1) + 120

Since the remainder is not equal to 0.

Apply lemma again on 150 and 120.

We get,

150 = (120 × 1) + 30

Since the remainder is not equal to 0.

Apply lemma again on 120 and 30.

We get,

120 = (30 × 4) + 0

The remainder is 0 now.

⇒ HCF (4052, 12576) = 30.

Thus, HCF of 4052 and 12576 is 30.