103 LearnersLast updated on July 4th, 2025
Euclid's Division Lemma
Euclid’s Division Lemma is a fundamental principle in number theory that describes the division of two integers. This lemma forms the basis of the Euclidean algorithm, used to compute the GCD of two numbers.
What is Euclid's Division Lemma
Euclid’s division lemma states there are two positive integers a and b, where a ≥ b, there exists a unique set of integers q and r, such that:
a = bq + r
This lemma is the foundation of the Euclidean algorithm, used for computing the GCD of two numbers.
Statement of Euclid’s Division Lemma
The statement of Euclid’s division lemma for any two positive integers a and b, where a ≥ b, there exists a unique set of integers q and r, such that:
a = bq + r, where q is the quotient and r is the remainder, 0 ≤ r < b.
Proof of Euclid's Division Lemma
For the proof of Euclid’s division lemma, let us consider the following arithmetic progression as: …, a - 3b, a - 2b, a - b, a, a + b, a + 2b, a + 3b,...
The above progression has a difference ‘b’, which extends indefinitely in both directions. Now let us consider the smallest non-negative term of this arithmetic progression to be r. The difference between the smallest non-negative term r and a will be a multiple of the common difference ‘b’ since both are in the arithmetic progression.
So we can write the arithmetic progression as:
a - r = bq
a = bq + r
where ‘r’ is the smallest non-negative integer, therefore, 0 ≤ r < b.
Let us now prove the uniqueness of q and r:
Let us consider another pair q’ and r’ such that a = bq’ + r’ and 0 ≤ r’ < b., then we have:
bq + r = bq’ + r’
b(q - q’) = r - r’
Since 0 ≤ r’ < b and 0 ≤ r < b.
Since, |r’ - r| < b and b divides (r - r’)
Therefore, if q = q’ and r = r’
Hence, it is proved that q and r are unique.
How to Find HCF By Euclid's Division Lemma?
Euclid’s division lemma is used to find the HCF of two given numbers. The steps to find the HCF of two numbers using Euclid’s division lemma is given below:
Let us take two numbers x and y for which we have to find the HCF using Euclid’s division lemma, such that x > y.
Step 1: First, we have to apply the Euclid’s division lemma to ‘x’ and ‘y’. We can find whole numbers, ‘q’ and ‘r’, such that x = yq + r, where 0 ≤ r < y.
Step 2: If r = 0, ‘y’ is the HCF of ‘x’ and ‘y’. If r not equal to 0, apply the division lemma again to ‘y’ and ‘r’.
Step 3: Till the remainder is 0, this division continues. The divisor at this stage will be the required HCF.
Common Mistakes and How to Avoid Them in Euclid's Division Lemma
Students tend to make mistakes while understanding the concept of Euclid's division lemma. Let us see some common mistakes and how to avoid them, in Euclid's division lemma:
Mistake 1
Confusing Euclid’s Division Lemma with Euclidean Algorithm:
Lemma states a = bq + r, where 0 ≤ r < b, while Euclidean algorithm uses the lemma to find the GCD.
Mistake 2
Incorrectly Defining the Remainder:
Students should always make sure that the remainder r is between 0 and b - 1. Euclid’s division lemma is used to understand the correct range for the remainder.
Mistake 3
Confusing Quotient and Remainder:
Students sometimes confuse the quotient and remainder. They should always perform long division carefully and ensure that 0 ≤ r < b.
Mistake 4
Assuming Euclid’s Lemma Works for All Number Systems:
Students must remember that the lemma only works for integers. They must remember that the lemma does not apply to non-integer values like fractions or decimals.
Mistake 5
Skipping Verification of the Lemma:
The students must practice verifying the lemma after solving the problem. They must substitute the values back into the equation to verify if they satisfy the condition.
Solved examples on Euclid's Division Lemma
Problem 1
Apply Euclid’s Division Lemma to 23 and 5.
Quotient q = 4, remainder r = 3.
Explanation
Using the lemma,
we express 23 in terms of 5:
a = bq + r where a = 23, b = 5, and 0 ≤ r < 5.
Perform division:
23 divided by 5 = 4 remainder 3
Thus:
23 = 5 x 4 + 3
Problem 2
Find q and r for 41 divided by 7 using Euclid’s Division Lemma
Quotient q = 5 and remainder r = 6.
Explanation
Divide 41 by 7:
41 divided by 7 = 5 remainder 6
So we write it as:
41 = 7 x 5 + 6.
Problem 3
Express 55 in terms of 9 using Euclid’s Lemma.
q = 6, r = 1
Explanation
Perform division:
55 9 = 6 remainder 1
Thus:
55 = 9 x 6 + 1
Problem 4
Express 100 in terms of 8 in Euclid’s Division Lemma
q = 12, r = 4
Explanation
Divide 100 by 8:
100 8 = 12 remainder 4
Thus:
100 = 8 x 12 + 4
Problem 5
Express 76 in terms of 11 using Euclid’s Division Lemma.
q = 6, r = 10
Explanation
Divide 76 by 11:
76 divided by 11 = 6 remainder 10
Thus,
76 = 11 x 6 + 10.
FAQs on Euclid's Division Lemma
1.What is Euclid’s Division Lemma?
2.What does the lemma formally state?
3.Why is Euclid’s Division Lemma important?
4.How does the lemma lead to the Euclidean algorithm?
5.What do the terms “quotient” and “remainder” mean in this context?
6.How can children in Singapore use numbers in everyday life to understand Euclid's Division Lemma?
7.What are some fun ways kids in Singapore can practice Euclid's Division Lemma with numbers?
8.What role do numbers and Euclid's Division Lemma play in helping children in Singapore develop problem-solving skills?
9.How can families in Singapore create number-rich environments to improve Euclid's Division Lemma skills?
Explore More numbers
![Important Math Links Icon]()
Previous to Euclid's Division Lemma
![Important Math Links Icon]()
Next to Euclid's Division Lemma
Hiralee Lalitkumar Makwana
About the Author
Hiralee Lalitkumar Makwana has almost two years of teaching experience. She is a number ninja as she loves numbers. Her interest in numbers can be seen in the way she cracks math puzzles and hidden patterns.
Fun Fact
: She loves to read number jokes and games.
