1 markMCQSection A

The HCF of 960 and 432 is :

(a) 48 (b) 54 (c) 72 (d) 36

Q: Can HCF be found without Euclid's algorithm?

Yes, via prime factorisation: express both numbers as products of primes and multiply the common primes raised to their lowest powers.

Real Numbers

HCF using Euclid's Division Algorithm

Options

(A)48

(B)54

(D)36

Official Answer

(a) 48 — by Euclid's algorithm, the last non-zero remainder in successive division of 960 and 432 is 48.

HCFEuclid's division algorithmgreatest common divisorprime factorisation960 and 432remainder

Marking Scheme

11 mark for selecting option (a) 48 with correct working (Euclid's algorithm or prime factorisation) shown if asked to justify.

Hint

Apply Euclid's Division Lemma repeatedly: $a = bq + r$ , until remainder $r = 0$ ; the last divisor is the HCF.

Quick Oral Answer

The HCF of 960 and 432 is 48, found using Euclid's Division Algorithm — divide repeatedly until the remainder is zero; the last non-zero divisor is the HCF.

Analysis & Explanation

Tests HCF using Euclid's Division Algorithm on two given numbers.

Concept

HCF (Highest Common Factor) can be found by Euclid's division lemma: $a = bq + r$ , repeated till remainder = 0; the last non-zero divisor is the HCF.

Key working

$960 = 432 \times 2 + 96$
$432 = 96 \times 4 + 48$
$96 = 48 \times 2 + 0 \to HCF = 48$
Cross-check by prime factorisation: $960 = 2^6 \times 3 \times 5$ , $432 = 2^4 \times 3^3$ , so $HCF = 2^4 \times 3 = 48$ .

Common mistakes

Arithmetic slips during repeated division steps.
Confusing HCF with LCM (LCM of 960, 432 = 8640, not asked here).
Picking 72 or 36 as they 'look like' factors of one number without checking they divide both exactly.

Real-world use

HCF is used to divide quantities into maximum equal groups, cut tiles/ropes of the largest common size, and reduce fractions to lowest terms.

Common Mistakes

1Stopping the division algorithm too early (before remainder reaches 0) and reporting an intermediate divisor as HCF.
2Confusing HCF (product of common prime factors with lowest powers) with LCM (product of all factors with highest powers).
3Arithmetic errors in successive division steps, especially $432 = 96 \times 4 + 48$ .

Interesting Facts

Euclid's Division Algorithm dates back to Euclid's 'Elements', written around 300 BCE, making it one of the oldest algorithms still taught and used today.

The algorithm is the basis of the modern computational method used in cryptography (RSA) for computing GCDs efficiently even for very large numbers.

Spotted a mistake or something unclear?

Tell us — we fix reported answers fast.

Frequently Asked Questions

What is Euclid's Division Algorithm?

It is a method to find the HCF of two positive integers a and b ( $a > b$ ) by repeatedly applying $a = bq + r (0 \le r < b)$ until the remainder becomes zero; the last non-zero divisor is the HCF.

Can HCF be found without Euclid's algorithm?