Find HCF(2032, 1651) by Euclid's algorithm.

Class 10Real NumbersNumber Systems

Step-by-Step Solution

2032 =

1651 \times 1 + 381

;

1651 = 381 \times 4 + 127

;

381 = 127 \times 3 + 0

. HCF = 127. Confirm:

2032 = 127 \times 16

and

1651 = 127 \times 13

. Reading off 381 stops the algorithm one line too early.

Answer: C) 127

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