RG's E-Learning Centre · Book a free demo class · WhatsApp +91-9379416374

Euclid's division algorithm for HCF: Class 10 practice

Euclid's division lemma: a = bq + r with 0 ≤ r < b. Read the method, follow the three worked examples, then try the six questions.

What you should know first

  • Long division

The idea behind euclid's division algorithm for hcf

Euclid's division lemma: a = bq + r with 0 ≤ r < b. Repeating it on (b, r) until the remainder is 0 gives the HCF as the last non-zero divisor.

Step-by-step method

  1. Divide the larger number by the smaller.
  2. Replace (a, b) by (b, r).
  3. Stop when r = 0; the divisor then is the HCF.

Worked example 1 (Basic)

Use Euclid's algorithm to find the HCF of 52 and 28.

  1. 52 = 28 × 1 + 24
  2. 28 = 24 × 1 + 4
  3. 24 = 4 × 6 + 0
  4. HCF = 4
  5. Answer: 4

Worked example 2 (Standard)

Use Euclid's algorithm to find the HCF of 740 and 600.

  1. 740 = 600 × 1 + 140
  2. 600 = 140 × 4 + 40
  3. 140 = 40 × 3 + 20
  4. 40 = 20 × 2 + 0
  5. HCF = 20
  6. Answer: 20

Worked example 3 (Challenge)

Use Euclid's algorithm to find the HCF of 2187 and 459.

  1. 2187 = 459 × 4 + 351
  2. 459 = 351 × 1 + 108
  3. 351 = 108 × 3 + 27
  4. 108 = 27 × 4 + 0
  5. HCF = 27
  6. Answer: 27

Common mistakes and misconceptions

  • Stopping one step early
  • Swapping the divisor and remainder

Practice questions

  1. (Basic) Use Euclid's algorithm to find the HCF of 476 and 350.
  2. (Basic) Use Euclid's algorithm to find the HCF of 81 and 15.
  3. (Standard) Use Euclid's algorithm to find the HCF of 264 and 143.
  4. (Standard) Use Euclid's algorithm to find the HCF of 448 and 252.
  5. (Challenge) Use Euclid's algorithm to find the HCF of 1023 and 297.
  6. (Challenge) Use Euclid's algorithm to find the HCF of 324 and 16.

Answer key with full working

  • Q1: 476 = 350 × 1 + 126 → 350 = 126 × 2 + 98 → 126 = 98 × 1 + 28 → 98 = 28 × 3 + 14 → 28 = 14 × 2 + 0 → HCF = 14 → Answer: 14
  • Q2: 81 = 15 × 5 + 6 → 15 = 6 × 2 + 3 → 6 = 3 × 2 + 0 → HCF = 3 → Answer: 3
  • Q3: 264 = 143 × 1 + 121 → 143 = 121 × 1 + 22 → 121 = 22 × 5 + 11 → 22 = 11 × 2 + 0 → HCF = 11 → Answer: 11
  • Q4: 448 = 252 × 1 + 196 → 252 = 196 × 1 + 56 → 196 = 56 × 3 + 28 → 56 = 28 × 2 + 0 → HCF = 28 → Answer: 28
  • Q5: 1023 = 297 × 3 + 132 → 297 = 132 × 2 + 33 → 132 = 33 × 4 + 0 → HCF = 33 → Answer: 33
  • Q6: 324 = 16 × 20 + 4 → 16 = 4 × 4 + 0 → HCF = 4 → Answer: 4

Syllabus note

This skill is listed under "Real Numbers" for Class 10 in the NCERT/CBSE books. ICSE, IGCSE, IB and state boards may teach it in a different chapter or year.

Answers on this page are generated and automatically re-checked by a second, independent calculation. They have not been reviewed by a teacher — if you spot a problem, tell us on WhatsApp.

Related practice and notes

Frequently asked questions

Which chapter is euclid's division algorithm for hcf in?

"Real Numbers", Class 10 Maths (NCERT/CBSE). Other boards may place it differently.

How were the answers checked?

Answers on this page are generated and automatically re-checked by a second, independent calculation. They have not been reviewed by a teacher — if you spot a problem, tell us on WhatsApp.

Book a free demo class