On this page
In Class 10 mathematics, the first chapter on real numbers introduces a technique for finding the highest common factor (HCF) of two integers without listing out all their factors. This technique relies on Euclid's division lemma and a process called Euclid's division algorithm. Much like the systematic rules for naming carbon compounds in chemistry, this algorithm offers a reliable procedure that replaces guesswork.
Though you learn it in school today, this method is one of the oldest mathematical algorithms still in common use. It was published around 300 BC in ancient Greece. Here is how the repeated division method works, why it always finds the highest common factor, and how you can apply it efficiently in your exams without making arithmetic mistakes.
What is Euclid's division lemma?
Before using the algorithm, you need to understand the lemma it is built upon. A lemma is a proven statement used as a stepping stone to prove other mathematical results.
Euclid's division lemma states that given two integers *a* and *b* (where *b ≠ 0*), there exist unique integers *q* (the quotient) and *r* (the remainder) such that *a = bq + r*, and *0 ≤ r < |b|* (Wikipedia).
This statement is simply the rigorous mathematical formalisation of the long division you learned in primary school. When you divide one positive number by another, you get a quotient and a remainder that is strictly smaller than the divisor. If the remainder *r* is zero, it means *b* divides *a* perfectly, so *b* is a factor of *a*. Understanding this fundamental rule is the key to mastering the algorithm.
How to find HCF using Euclid's division algorithm?
An algorithm is a series of well-defined steps designed to solve a specific problem. Euclid's division algorithm uses the division lemma repeatedly to find the greatest common divisor, or HCF.
The logic rests on a very simple but powerful property: the HCF of two numbers does not change if the larger number is replaced by its remainder after division (Wikipedia). Therefore, the HCF of *a* and *b* is exactly the same as the HCF of *b* and *r*. By replacing our large numbers with smaller ones (the divisor and the remainder) at each step, the problem becomes progressively simpler.
Here is the step-by-step framework to find the HCF of two positive integers, *c* and *d* (where *c > d*):
Apply the lemma: Divide *c* by *d* to find the quotient *q* and the remainder *r* (so that *c = d × q + r*).
Check the remainder: If *r = 0*, then the HCF is *d*. You can stop here.
Repeat if necessary: If *r ≠ 0*, apply the division lemma again. This time, use *d* as the new dividend and *r* as the new divisor.
Continue: Keep repeating this division process until the remainder is zero. The divisor at that final stage is the HCF.
A worked example: HCF of 252 and 105
Let's find the HCF of 252 and 105 using this repeated division method.
Step 1: Divide 252 by 105. 252 = 105 × 2 + 42. (The quotient is 2, and the remainder is 42).
Step 2: The remainder is not zero, so divide the previous divisor (105) by the remainder (42). 105 = 42 × 2 + 21. (The quotient is 2, and the remainder is 21).
Step 3: The remainder is still not zero. Divide 42 by 21. 42 = 21 × 2 + 0. (The quotient is 2, and the remainder is 0).
Since the remainder is now zero, the divisor at this step—which is 21—is our highest common factor. The procedure guarantees that we will always reach a zero remainder eventually.
If you get stuck on the arithmetic or reasoning in problems like this, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
What is the history of Euclid's algorithm?
The algorithm is named after the ancient Greek mathematician Euclid, who first described it in his famous treatise *Elements* around 300 BC. The *Elements* is a collection of 13 books that heavily influenced Western mathematics, assembling geometric and mathematical knowledge into a rigorous, logical order.
Interestingly, Euclid originally formulated this algorithm geometrically rather than algebraically. The ancient Greeks thought of numbers as lengths of physical line segments. To find the greatest common divisor of two lengths, Euclid would subtract the shorter length from the longer length repeatedly until a common measure was found that could measure both lengths exactly.
The algorithm was later generalised to work with other algebraic structures. In the 19th century, mathematicians extended it to polynomials, laying the groundwork for more advanced algebraic topics you will encounter in higher mathematics, such as checking when a quadratic is always positive.
For students who want to explore these connections further, the Fermi Concept Library contains every concept in physics, chemistry, biology, mathematics and computing, each with its own lesson and its place in the map.
