Question 11 markMCQSection A

The HCF of 960 and 432 is :

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

Real Numbers
HCF using Euclid's Division Algorithm

Options

(A)48
(B)54
(C)72
(D)36

Official answer

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

Answer keywords:HCFEuclid's division algorithmgreatest common divisorprime factorisation960 and 432remainder

Marking scheme

  1. 1.1 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+ra = bq + r, until remainder r=0r = 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.

Common mistakes

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

Analysis and 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+ra = bq + r, repeated till remainder = 0; the last non-zero divisor is the HCF.

Key working

  • 960=432×2+96960 = 432 \times 2 + 96
  • 432=96×4+48432 = 96 \times 4 + 48
  • 96=48×2+0→HCF=4896 = 48 \times 2 + 0 \to HCF = 48
  • Cross-check by prime factorisation: 960=26×3×5960 = 2^6 \times 3 \times 5, 432=24×33432 = 2^4 \times 3^3, so HCF=24×3=48HCF = 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.

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.

Question details

Q1 of 56 questions

Board
CBSE
Class
Class 10
Subject
Mathematics (Standard)
Year
2026
Section
Section A
Marks
1
Type
MCQ
Chapter
Real Numbers
Topic
HCF using Euclid's Division Algorithm
Bloom's level
apply
Syllabus topic
Unit 1: Number Systems — Real Numbers: Euclid's Division Lemma / HCF by Division Method
Author
CBSE
Reviewed by
Padhantu Academic Team

Spotted a mistake or something unclear?

Tell us and we will fix it.

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>ba > b) by repeatedly applying a=bq+r(0≤r<b)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?

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