Euclidean Algorithm: HCF Formula, Method and Examples
Euclidean Algorithm finds the HCF of two positive integers through repeated division. It replaces the larger number with the remainder after division until the remainder becomes zero. The last non-zero remainder is the HCF. This page explains the formula, division steps, useful shortcuts, properties and numerical examples used in quantitative aptitude.
What is the Euclidean Algorithm?
For positive integers a and b, where a ≥ b, the basic rule is HCF(a, b) = HCF(b, a mod b). Continue the process until the remainder is 0. The divisor in the final division is the HCF. For example, 252 = 105 × 2 + 42, 105 = 42 × 2 + 21, and 42 = 21 × 2 + 0. Therefore, HCF(252, 105) = 21.
Euclidean Algorithm Formula & Tricks
Important Formulas
The HCF does not change when the larger number is replaced by the remainder obtained on division by the smaller number.
Here, a is the dividend, b is the divisor, q is the quotient and r is the remainder.
When the remainder becomes zero, the divisor of that final division is the HCF.
Quick Tricks
Do not continue after a zero remainder. The divisor in that line is the HCF.
The property HCF(a, b) = HCF(a − b, b) can reduce calculations when the numbers are close. Repeat subtraction or combine it with division.
If both numbers have an obvious common factor, divide it out, find the HCF of the reduced numbers, and multiply the result by that factor.
Euclidean Algorithm Concepts
Division Steps in the Euclidean Method
Write each step in the form dividend = divisor × quotient + remainder. Continue while the remainder is non-zero. The last non-zero remainder gives the HCF.
Why the Remainder Rule Works
If a = bq + r, then r = a − bq. Every common divisor of a and b divides r, and every common divisor of b and r divides a. Therefore, HCF(a, b) = HCF(b, r).
Difference Property of HCF
Subtracting the smaller number from the larger one preserves the set of common divisors. Repeated subtraction is equivalent to repeated division, but division is usually faster for large numbers.
Handling More Than Two Numbers
For three numbers, HCF(a, b, c) = HCF(HCF(a, b), c). This process can be continued for any number of integers.
Co-Prime Numbers and Termination
If the final non-zero remainder is 1, the numbers have no common factor greater than 1. If one number divides the other exactly, the smaller number is the HCF after the first division.
Euclidean Algorithm Video Lessons
Watch short topic-wise lessons for quick revision.
HCF Using Prime Factorisation and Euclidean Algorithm
Learn to calculate the Highest Common Factor using prime factorisation and the Euclidean algorithm, with a clear understanding of how both methods work.
Practice Euclidean Algorithm Questions
Practise published questions related to this topic.
Euclidean Algorithm Quick Quiz
Attempt 5 questions and check your score instantly.
Keep practising
Practice more Euclidean Algorithm questions in the PrepShots app and continue from your current topic.
Practice More Questions - Start ₹1 Trial →Quick Revision Notes
Euclidean Algorithm Quick Revision
Use repeated division to reduce the pair of numbers until the remainder becomes zero.
- For a ≥ b > 0, use HCF(a, b) = HCF(b, a mod b).
- Write every division as a = bq + r, with 0 ≤ r < b.
- The divisor in the final division with zero remainder is the HCF.
- The difference property is HCF(a, b) = HCF(a − b, b) when a > b.
- For multiple numbers, apply the algorithm successively: HCF(a, b, c) = HCF(HCF(a, b), c).
- A final non-zero remainder of 1 means the numbers are co-prime.
- If b divides a exactly, HCF(a, b) = b.
Euclidean Algorithm FAQs
What is the Euclidean Algorithm formula for HCF?
The formula is HCF(a, b) = HCF(b, a mod b), where a ≥ b > 0. Repeat this replacement until the remainder is zero.
How is HCF(252, 105) found using the division method?
252 = 105 × 2 + 42, 105 = 42 × 2 + 21, and 42 = 21 × 2 + 0. Therefore, HCF(252, 105) = 21.
What is the HCF when one number divides the other exactly?
The smaller number is the HCF. For example, since 72 = 24 × 3, HCF(72, 24) = 24.
Can the Euclidean Algorithm be used for three numbers?
Yes. Find the HCF of two numbers and then use that result with the third: HCF(a, b, c) = HCF(HCF(a, b), c).
What does a final non-zero remainder of 1 indicate?
It indicates that the two numbers are co-prime, so their HCF is 1. For example, HCF(35, 64) = 1.
What is the difference between the Euclidean Algorithm and the HCF division method?
They are the same repeated-division procedure. In both methods, the last non-zero remainder is the HCF.