HCF by Euclid's Division Algorithm
Euclid's Division Algorithm is a method for finding the HCF of two positive integers through repeated division.
Unlike prime factorisation, this algorithm does not require finding prime factors — making it remarkably efficient for large numbers.
Key facts:
- Based on Euclid's Division Lemma (CBSE Class 10, Chapter 1: Real Numbers)
- Described by Euclid over 2,300 years ago in Book VII of Elements
- Still used in modern computer science (RSA cryptography, GCD functions)
- Works through simple divisions — no factorisation needed
What is HCF by Euclid's Algorithm?
Definition: Euclid's Division Algorithm is a step-by-step procedure to find the HCF of two positive integers, based on the principle HCF(a, b) = HCF(b, r), where a = bq + r.
Steps to find HCF:
- Start with two positive integers a and b, where a ≥ b. (If a < b, swap them.)
- Divide a by b to get quotient q and remainder r. Write a = b × q + r.
- If r = 0, then b is the HCF. Stop.
- If r ≠ 0, replace a with b and b with r. Go back to step 2.
- Repeat until remainder = 0. The last non-zero remainder is the HCF.
Example — HCF(270, 21):
- 270 = 21 × 12 + 18 (r = 18 ≠ 0)
- 21 = 18 × 1 + 3 (r = 3 ≠ 0)
- 18 = 3 × 6 + 0 (r = 0, stop)
HCF(270, 21) = 3.
Why this works:
- At each step, HCF(a, b) = HCF(b, r).
- Remainders form a strictly decreasing sequence: b > r₁ > r₂ > ... ≥ 0.
- The algorithm must terminate with remainder 0 in finite steps.
Comparison with prime factorisation:
- Euclid's Algorithm is faster for large numbers (no factorisation needed).
- Prime factorisation gives both HCF and LCM; Euclid's gives only HCF directly.
HCF by Euclid's Division Algorithm Formula
Key formulas:
HCF(a, b) = HCF(b, r) where a = bq + r, 0 ≤ r < b
Related formulas:
- Termination: HCF(a, 0) = a. When remainder reaches 0, the other number is the HCF.
- Finding LCM after HCF: LCM(a, b) = (a × b) / HCF(a, b).
- Extended Euclidean Algorithm: There exist integers x, y such that HCF(a, b) = ax + by (Bezout's Identity).
- Step count: The algorithm takes at most 5 × (number of digits of the smaller number) steps.
Algorithm in tabular form:
| Step | Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|---|
| 1 | a | b | q₁ | r₁ |
| 2 | b | r₁ | q₂ | r₂ |
| 3 | r₁ | r₂ | q₃ | r₃ |
| ... | ... | ... | ... | ... |
| n | rₖ₋₂ | rₖ₋₁ | qₖ | 0 |
HCF = rₖ₋₁ (the last non-zero remainder).
Derivation and Proof
Proof that Euclid's Algorithm correctly finds HCF
Part 1: The algorithm terminates
- At each step, a = bq + r where 0 ≤ r < b.
- The new remainder r' satisfies 0 ≤ r' < r.
- Remainders form a strictly decreasing sequence: b > r₁ > r₂ > r₃ > ... ≥ 0.
- A strictly decreasing sequence of non-negative integers must reach 0. Algorithm terminates.
Part 2: The final non-zero remainder is the HCF
Key lemma: If a = bq + r, then HCF(a, b) = HCF(b, r).
Proof of key lemma:
- Let d be any common divisor of a and b. Then d | a and d | b, so d | (a − bq) = r. Hence d divides both b and r.
- Conversely, let d be any common divisor of b and r. Then d | b and d | r, so d | (bq + r) = a. Hence d divides both a and b.
- The common divisors of (a, b) are identical to the common divisors of (b, r).
- Therefore HCF(a, b) = HCF(b, r).
Applying repeatedly:
HCF(a, b) = HCF(b, r₁) = HCF(r₁, r₂) = ... = HCF(rₖ₋₁, 0) = rₖ₋₁. QED.
Efficiency:
- Gabriel Lame (1844) proved the step count never exceeds 5 × (digits of smaller number).
- Worst case: consecutive Fibonacci numbers (quotient 1 at every step, slowest decrease).
- Example worst case — HCF(89, 55): takes 9 steps because 89 and 55 are consecutive Fibonacci numbers.
Types and Properties
Types of problems using Euclid's Algorithm:
Type 1: Direct HCF computation
Given two positive integers, find their HCF step by step.
Type 2: HCF of three or more numbers
Find HCF(a, b, c) = HCF(HCF(a, b), c). Apply the algorithm twice.
Type 3: Word problems requiring HCF
Keywords: "largest", "greatest", "maximum", "divide equally", "measure exactly".
Type 4: Proof questions
Show that HCF(a, b) = HCF(b, r) using the property of common divisors.
Type 5: Combined with LCM
Find HCF using the algorithm, then use LCM = (a × b) / HCF.
Type 6: Linear combination (Bezout's Identity)
Express HCF(a, b) as ax + by by back-substituting through algorithm steps.
Euclid's Algorithm vs Prime Factorisation:
| Feature | Euclid's Algorithm | Prime Factorisation |
|---|---|---|
| Speed for large numbers | Very fast | Slow (factorisation is hard) |
| Gives LCM directly? | No (separate calculation) | Yes |
| Mental math friendly? | Yes (just divide) | Harder (need all factors) |
| Works for any size | Yes | Impractical for very large numbers |
Solved Examples
Example 1: Basic HCF computation with two numbers
Problem: Find the HCF of 468 and 222 using Euclid's Division Algorithm.
Solution:
- 468 = 222 × 2 + 24 (r = 24 ≠ 0)
- 222 = 24 × 9 + 6 (r = 6 ≠ 0)
- 24 = 6 × 4 + 0 (r = 0, stop)
Last non-zero remainder = 6.
Answer: HCF(468, 222) = 6.
Example 2: HCF where one number is much larger
Problem: Find HCF(7344, 1260) using Euclid's Algorithm.
Solution:
- 7344 = 1260 × 5 + 1044
- 1260 = 1044 × 1 + 216
- 1044 = 216 × 4 + 180
- 216 = 180 × 1 + 36
- 180 = 36 × 5 + 0
HCF = 36.
Verification: 7344/36 = 204 ✓ and 1260/36 = 35 ✓.
Answer: HCF(7344, 1260) = 36.
Example 3: HCF of coprime numbers
Problem: Find HCF(847, 2160) using Euclid's Algorithm.
Solution:
- 2160 = 847 × 2 + 466
- 847 = 466 × 1 + 381
- 466 = 381 × 1 + 85
- 381 = 85 × 4 + 41
- 85 = 41 × 2 + 3
- 41 = 3 × 13 + 2
- 3 = 2 × 1 + 1
- 2 = 1 × 2 + 0
HCF = 1. The numbers are coprime.
Answer: HCF(847, 2160) = 1.
Example 4: HCF of three numbers using the algorithm
Problem: Find HCF(408, 1032, 312) using Euclid's Division Algorithm.
Solution:
Step A — Find HCF(408, 1032):
- 1032 = 408 × 2 + 216
- 408 = 216 × 1 + 192
- 216 = 192 × 1 + 24
- 192 = 24 × 8 + 0
HCF(408, 1032) = 24.
Step B — Find HCF(24, 312):
- 312 = 24 × 13 + 0
HCF(24, 312) = 24.
Answer: HCF(408, 1032, 312) = 24.
Example 5: Finding LCM after computing HCF by Euclid's Algorithm
Problem: Find the HCF and LCM of 1260 and 7560 using Euclid's Algorithm.
Solution:
HCF:
- 7560 = 1260 × 6 + 0 (remainder 0 in first step!)
HCF = 1260. (1260 divides 7560 exactly.)
LCM:
- LCM = (a × b) / HCF = (1260 × 7560) / 1260 = 7560
When one number divides the other: HCF = smaller number, LCM = larger number.
Answer: HCF = 1260, LCM = 7560.
Example 6: Word problem — Equal distribution (HCF)
Problem: A merchant has 120 kg sugar, 168 kg rice, and 264 kg flour. He wants equal-weight bags, each containing only one item type. What is the heaviest possible bag?
Solution:
Given: Maximum bag weight = HCF(120, 168, 264).
Step A — HCF(120, 168):
- 168 = 120 × 1 + 48
- 120 = 48 × 2 + 24
- 48 = 24 × 2 + 0
HCF(120, 168) = 24.
Step B — HCF(24, 264):
- 264 = 24 × 11 + 0
HCF(24, 264) = 24.
Number of bags:
- Sugar: 120/24 = 5
- Rice: 168/24 = 7
- Flour: 264/24 = 11
- Total = 23 bags
Answer: Heaviest bag = 24 kg. Total bags = 23.
Example 7: Word problem — Dance group formation
Problem: 117 girls and 130 boys participate in a dance programme. Each group must be all-boys or all-girls with equal group size. Find the maximum group size.
Solution:
Given: Maximum group size = HCF(117, 130).
- 130 = 117 × 1 + 13
- 117 = 13 × 9 + 0
HCF = 13.
Number of groups:
- Girl groups: 117/13 = 9
- Boy groups: 130/13 = 10
- Total = 19 groups
Answer: Maximum group size = 13. Total groups = 19.
Example 8: When one number is a factor of the other
Problem: Find HCF(1575, 225) using Euclid's Algorithm.
Solution:
- 1575 = 225 × 7 + 0 (remainder 0 immediately)
225 divides 1575 exactly (1575 = 225 × 7).
Answer: HCF(1575, 225) = 225.
Example 9: Challenging problem — Finding the HCF for a remainder condition
Problem: Find the greatest number which divides 285 and 1249, leaving remainders 9 and 7 respectively.
Solution:
Given:
- The number divides (285 − 9) = 276 and (1249 − 7) = 1242 exactly
- Required = HCF(276, 1242)
Using Euclid's Algorithm:
- 1242 = 276 × 4 + 138
- 276 = 138 × 2 + 0
HCF = 138.
Verification: 285 = 138 × 2 + 9 ✓. 1249 = 138 × 9 + 7 ✓.
Answer: The greatest such number is 138.
Example 10: Expressing HCF as a linear combination (bonus challenge)
Problem: Find HCF(161, 28) and express it as 161x + 28y.
Solution:
Forward pass (find HCF):
- 161 = 28 × 5 + 21 ... (i)
- 28 = 21 × 1 + 7 ... (ii)
- 21 = 7 × 3 + 0
HCF = 7.
Backward substitution:
- From (ii): 7 = 28 − 21 × 1
- From (i): 21 = 161 − 28 × 5. Substitute:
- 7 = 28 − (161 − 28 × 5) × 1 = 28 × 6 − 161 × 1
- 7 = 161 × (−1) + 28 × 6
Verification: 161 × (−1) + 28 × 6 = −161 + 168 = 7 ✓
Answer: HCF(161, 28) = 7 = 161(−1) + 28(6).
Real-World Applications
Applications of Euclid's Division Algorithm:
- Cryptography (RSA): The Extended Euclidean Algorithm computes modular multiplicative inverses, which are essential for RSA encryption used in internet banking and secure communications.
- Computer Programming: Built-in GCD functions in all major languages (Python's
math.gcd(), Java'sBigInteger.gcd(), C++'s__gcd()) implement this algorithm. - Reducing Fractions: Divide numerator and denominator by HCF. Example: 84/126 → HCF(84, 126) = 42 → 84/126 = 2/3.
- Gear Ratios: Simplifying gear teeth ratios. A system with 84 and 126 teeth simplifies to 2:3 using HCF = 42.
- Map Scaling: Simplifying distance ratios. 84 cm representing 126 km uses scale 2:3.
- Music Theory: The Euclidean rhythm algorithm distributes beats evenly in a time signature using this algorithm directly.
Key Points to Remember
- Euclid's Algorithm: Repeatedly apply a = bq + r until r = 0. The last non-zero remainder is the HCF.
- Based on: HCF(a, b) = HCF(b, r) where a = bq + r.
- Always terminates because remainders form a strictly decreasing sequence of non-negative integers.
- When r = 0 in the first step, the smaller number divides the larger, and HCF = smaller number.
- For three numbers: HCF(a, b, c) = HCF(HCF(a, b), c). Apply the algorithm twice.
- After finding HCF, compute LCM using: LCM = (a × b) / HCF.
- Euclid's Algorithm is faster than prime factorisation for large numbers.
- For remainder-based problems: subtract remainders from each number, then find HCF.
- Takes at most 5 × (digits of smaller number) steps.
- This topic carries 2–3 marks in CBSE board exams. Show all division steps for full marks.
Practice Problems
- Use Euclid's Division Algorithm to find the HCF of 960 and 432.
- Find HCF(1288, 575) using Euclid's Algorithm and verify by checking if the HCF divides both numbers.
- Use Euclid's Algorithm to find the HCF of 4032, 262, and 1776.
- Find the HCF and then the LCM of 3024 and 2520 using Euclid's Algorithm.
- An electronic display shows a blinking dot. If one dot blinks every 18 seconds and another every 24 seconds, after how many seconds will both blink together? (Use Euclid's Algorithm to find HCF first, then compute LCM.)
- The length, breadth, and height of a room are 825 cm, 675 cm, and 450 cm respectively. Find the longest tape which can measure all three dimensions exactly. Use Euclid's Algorithm.
- Find the greatest number that will divide 445, 572, and 699, leaving remainders 4, 5, and 6 respectively.
- Use Euclid's Algorithm to show that HCF(65, 26) = 13, and express 13 as a linear combination 65x + 26y for integers x and y.
Frequently Asked Questions
Q1. What is Euclid's Division Algorithm for finding HCF?
Euclid's Division Algorithm finds the HCF by repeatedly dividing and taking remainders. Divide the larger number by the smaller. Then divide the previous divisor by the remainder. Continue until the remainder is 0. The last non-zero remainder is the HCF.
Q2. How is Euclid's Algorithm different from the prime factorisation method?
Euclid's Algorithm uses repeated division without needing prime factors. Prime factorisation requires breaking numbers into primes first. Euclid's Algorithm is faster for large numbers but gives only HCF (not LCM). Prime factorisation gives both HCF and LCM.
Q3. Why does Euclid's Algorithm work?
Because HCF(a, b) = HCF(b, r) where a = bq + r. Any number dividing both a and b must also divide r (since r = a - bq). Conversely, any number dividing b and r must divide a. So the common divisors of (a, b) and (b, r) are identical, and their HCFs are equal.
Q4. How many steps does Euclid's Algorithm take?
At most 5 times the number of digits of the smaller number. For two 3-digit numbers, at most 15 steps (though usually far fewer). The worst case occurs with consecutive Fibonacci numbers. Most classroom problems finish in 3 to 6 steps.
Q5. Can Euclid's Algorithm be used for three numbers?
Yes. Find HCF of the first two numbers, then find HCF of that result with the third number. HCF(a, b, c) = HCF(HCF(a, b), c). This extends to any count of integers.
Q6. How to find LCM using Euclid's Algorithm?
Euclid's Algorithm gives only HCF. To find LCM, use the formula: LCM(a, b) = (a × b) / HCF(a, b). Example: HCF(12, 18) = 6, so LCM = (12 × 18) / 6 = 36.
Q7. What if the first division in Euclid's Algorithm gives remainder 0?
Then the smaller number divides the larger number exactly, and the HCF is the smaller number. Example: HCF(36, 108): 108 = 36 × 3 + 0, so HCF = 36.
Q8. What is the difference between Euclid's Division Lemma and Euclid's Division Algorithm?
The lemma is the mathematical statement: for any a and b, there exist unique q and r with a = bq + r and 0 ≤ r < b. The algorithm is the step-by-step procedure that uses this lemma repeatedly to find the HCF. The lemma is the theoretical foundation; the algorithm is the practical method.
Q9. Is Euclid's Algorithm still used in modern technology?
Yes. It is used in RSA encryption (internet security), computer algebra systems, signal processing, and error-correcting codes. The Extended Euclidean Algorithm (finding x, y in HCF = ax + by) is essential for modular arithmetic in cryptography.
Q10. What are common mistakes students make with Euclid's Algorithm?
Common mistakes: (1) Not starting with the larger number as dividend, (2) Arithmetic errors in long division, (3) Stopping too early (before remainder is 0), (4) Taking the wrong remainder as HCF (must be the LAST non-zero remainder), (5) Not showing all steps in board exams. Always verify by checking the HCF divides both numbers.
