Using Euclid's division algorithm, find HCF(1224, 1080).

Class 10Real NumbersNumber Systems

Step-by-Step Solution

1224 =

1080 \times 1 + 144

;

1080 = 144 \times 7 + 72

;

144 = 72 \times 2 + 0

. The last non-zero remainder is 72, so HCF = 72. Check by primes:

1224 = 2^{3} \cdot 3^{2}

·17 and

1080 = 2^{3} \cdot 3^{3}

·5, common part

2^{3} \cdot 3^{2} = 72

. Stopping at the first remainder gives 144; 36 and 24 are common factors but not the HIGHEST one.

Answer: C) 72

**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.