Apply Euclid's algorithm to 3556 and 3444. Their HCF is:

Class 10Real NumbersNumber Systems

Step-by-Step Solution

3556 =

3444 \times 1 + 112

;

3444 = 112 \times 30 + 84

;

112 = 84 \times 1 + 28

;

84 = 28 \times 3 + 0

, so HCF = 28. In primes

3556 = 2^{2}

·7·127 and

3444 = 2^{2}

·3·7·41, and only

2^{2}

·7 = 28 is shared. Reading off the first remainder 112 is the usual slip, and 56 does not divide 3444.

Answer: A) 28

**Lemma**: For positive integers a,

b

(with

b > 0

), there exist UNIQUE

q, r

with

a = b q + r

and 0 ≤

r < b

.

This is just formal long division —

q

is the quotient,

r

is the remainder.

**Algorithm to find HCF(a, b)** with

a > b

:
1. Apply lemma:

a = b q + r

.
2. If

r = 0

, HCF =

b

.
3. If

r

≠ 0, replace (a, b) with

(b

, r) and repeat.

**Example**: HCF(420, 130)

. - 420 = 130 \times 3 + 30 - 130 = 30 \times 4 + 10 - 30 = 10 \times 3 + 0

→ HCF = 10.

Don't just memorise the answer — build a daily practice habit.