# Euclid’s Division Lemma: Statement, Proof, Formula and Solved Examples
## Introduction
Euclid’s Division Lemma is one of the fundamental results in number theory. It explains the mathematical relationship between a dividend, a divisor, a quotient, and a remainder. The lemma is particularly important because it provides the foundation for the Euclidean algorithm, a systematic method for finding the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two positive integers.
When we divide one positive integer by another, we obtain a quotient and a remainder. For example, dividing 23 by 5 gives a quotient of 4 and a remainder of 3. This can be written as 23 = 5 × 4 + 3.
Euclid’s Division Lemma expresses this relationship in a general mathematical form. It establishes that, for a positive integer a and a positive integer b, there exist unique integers q and r satisfying:
**a = bq + r, where 0 ≤ r < b**
In this equation, a is the dividend, b is the divisor, q is the quotient, and r is the remainder.
The condition 0 ≤ r < b is essential. It means that the remainder cannot be negative and must always be smaller than the divisor. This condition ensures that every integer has a unique quotient-and-remainder representation for a fixed positive divisor.
The lemma is studied in school mathematics, especially in number theory and chapters related to real numbers, divisibility, and HCF. Understanding it also prepares students to learn the Euclidean algorithm, prime factorisation, and other important results involving integers.
## 1. What Is Euclid’s Division Lemma?
Euclid’s Division Lemma is a mathematical statement that describes the division of integers using a quotient and a remainder.
It states that if a and b are positive integers, then there exist unique integers q and r such that:
a = bq + r
with the conditions:
0 ≤ r < b
The equation represents the original number as the sum of a multiple of the divisor and a remainder.
For example, consider the division of 31 by 6.
We know that:
31 = 6 × 5 + 1
Here, the dividend is 31, the divisor is 6, the quotient is 5, and the remainder is 1.
The remainder satisfies the required condition because:
0 ≤ 1 < 6
Therefore, the representation follows Euclid’s Division Lemma.
### Understanding the four components
**Dividend (a):** The number that is being divided.
**Divisor (b):** The positive number by which the dividend is divided.
**Quotient (q):** The integer representing the number of complete groups of size b contained in a.
**Remainder (r):** The non-negative amount left after taking out those complete groups.
For instance, in 47 = 9 × 5 + 2, the dividend is 47, the divisor is 9, the quotient is 5, and the remainder is 2.
The divisor must be positive because division by zero is undefined. The remainder must be smaller than the divisor because, if the remainder were equal to or greater than the divisor, another complete group could be taken out.
## 2. Statement of Euclid’s Division Lemma
The formal statement is:
**For any two positive integers a and b, there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b.**
This statement contains three important ideas.
First, every positive integer can be divided by another positive integer to obtain an integer quotient and a remainder.
Second, the remainder is always non-negative and strictly less than the divisor.
Third, the quotient and remainder are unique for a given dividend and positive divisor.
For example, consider a = 50 and b = 7.
The correct representation is:
50 = 7 × 7 + 1
The quotient is 7 and the remainder is 1.
We cannot represent 50 as 7 × 6 + 8 under the lemma because the remainder 8 is greater than the divisor 7. Although 7 × 6 + 8 equals 50 arithmetically, it does not satisfy the remainder condition.
Similarly, 50 = 7 × 8 − 6 is not a valid division representation under the lemma because the remainder is negative.
These examples demonstrate why both conditions on r are necessary.
## 3. Mathematical Formula and Meaning
The general formula is:
a = bq + r
where:
- a is the dividend.
- b is the positive divisor.
- q is the integer quotient.
- r is the remainder.
- 0 ≤ r < b.
The formula can also be rearranged to calculate the quotient when the other values are known:
q = (a − r) / b
Similarly, the remainder can be calculated as:
r = a − bq
These rearrangements are useful when checking whether a proposed quotient and remainder are correct.
### Example
Suppose a = 68 and b = 9.
The quotient is 7 because 9 × 7 = 63, and the remaining amount is 5.
Therefore:
68 = 9 × 7 + 5
Check the remainder condition:
0 ≤ 5 < 9
The condition holds, so q = 7 and r = 5.
### Why must the remainder be smaller than the divisor?
Suppose a number is divided by 8 and the proposed remainder is 11. The remainder is too large because 11 contains at least one complete group of 8.
We can rewrite:
8q + 11 = 8(q + 1) + 3
The quotient can increase by one, leaving a remainder of 3. Therefore, a remainder greater than or equal to the divisor can always be reduced to a valid remainder.
The restriction 0 ≤ r < b guarantees that the division process has reached its proper quotient and remainder.
## 4. Proof of Euclid’s Division Lemma
A theorem must be supported by a mathematical proof. One standard proof of Euclid’s Division Lemma uses the well-ordering principle for non-negative integers.
The well-ordering principle states that every non-empty set of non-negative integers contains a smallest element.
We will use this principle to prove the existence of q and r, then show that the quotient and remainder are unique.
### Part A: Proving existence
Let a and b be positive integers, with b greater than zero.
Consider the set of all non-negative integers of the form:
a − bk
where k is a non-negative integer and a − bk is non-negative.
Define the set:
S = {a − bk : k is a non-negative integer and a − bk ≥ 0}
This set is non-empty because choosing k = 0 gives a − b × 0 = a, which is non-negative.
By the well-ordering principle, S has a smallest element. Let this smallest element be r.
Thus:
r = a − bq
for some non-negative integer q.
Rearranging gives:
a = bq + r
We have obtained the required equation. Now we must show that the remainder satisfies 0 ≤ r < b.
Since r belongs to S, it is non-negative:
r ≥ 0
Suppose, for contradiction, that r ≥ b.
Then:
r − b ≥ 0
Using r = a − bq:
r − b = a − bq − b
r − b = a − b(q + 1)
This means r − b is another non-negative integer of the form a − bk. It therefore belongs to S.
But r − b is smaller than r because b is positive.
That contradicts the fact that r is the smallest element of S.
Therefore, our assumption was false, and we must have:
r < b
Combining the two conditions gives:
0 ≤ r < b
Hence, there exist integers q and r such that:
a = bq + r, where 0 ≤ r < b.
This proves the existence of the quotient and remainder.
### Part B: Proving uniqueness
Now suppose the same positive integers a and b have two valid representations:
a = bq₁ + r₁
and
a = bq₂ + r₂
where:
0 ≤ r₁ < b
0 ≤ r₂ < b
Since both expressions equal a, we can equate them:
bq₁ + r₁ = bq₂ + r₂
Rearranging:
b(q₁ − q₂) = r₂ − r₁
The left-hand side is an integer multiple of b.
Because both remainders lie between 0 and b − 1, their difference must satisfy:
−b < r₂ − r₁ < b
The only integer multiple of b strictly between −b and b is zero.
Therefore:
r₂ − r₁ = 0
So:
r₁ = r₂
Substituting equal remainders into the original equation gives:
bq₁ = bq₂
Since b is positive and therefore non-zero:
q₁ = q₂
Thus, both the quotient and remainder are unique.
The existence and uniqueness parts together complete the proof of Euclid’s Division Lemma.
## 5. Solved Examples of Euclid’s Division Lemma
Worked examples make it easier to understand how the lemma applies to different pairs of integers.
### Example 1: Divide 17 by 5
Express 17 in the form a = bq + r.
Given:
a = 17, b = 5
Find the largest multiple of 5 that does not exceed 17:
5 × 3 = 15
Subtract:
17 − 15 = 2
Therefore:
17 = 5 × 3 + 2
The quotient is 3 and the remainder is 2.
Check:
0 ≤ 2 < 5
Hence, the representation is correct.
### Example 2: Divide 45 by 7
Given:
a = 45, b = 7
The largest multiple of 7 that does not exceed 45 is:
7 × 6 = 42
The remainder is:
45 − 42 = 3
Therefore:
45 = 7 × 6 + 3
Here, q = 6 and r = 3.
Since 0 ≤ 3 < 7, the lemma is satisfied.
### Example 3: Divide 100 by 9
Given:
a = 100, b = 9
Calculate the quotient:
9 × 11 = 99
Calculate the remainder:
100 − 99 = 1
Therefore:
100 = 9 × 11 + 1
The quotient is 11 and the remainder is 1.
### Example 4: Divide 156 by 12
Given:
a = 156, b = 12
We have:
12 × 13 = 156
Therefore:
156 = 12 × 13 + 0
The quotient is 13 and the remainder is 0.
A remainder of zero means that 156 is exactly divisible by 12.
The condition 0 ≤ 0 < 12 is satisfied.
### Example 5: Find the quotient and remainder
Suppose a = 83 and b = 10.
Using the division formula:
83 = 10q + r
The largest multiple of 10 not exceeding 83 is 80.
Therefore:
83 = 10 × 8 + 3
So q = 8 and r = 3.
### Example 6: Check a proposed representation
Is 73 = 8 × 8 + 9 a valid representation under Euclid’s Division Lemma?
First, calculate the right-hand side:
8 × 8 + 9 = 64 + 9 = 73
The equality is correct, but the proposed remainder is 9 while the divisor is 8.
The condition r < b is not satisfied.
Therefore, it is not a valid quotient-and-remainder representation under the lemma.
The correct representation is:
73 = 8 × 9 + 1
Here, the quotient is 9 and the remainder is 1.
### Example 7: Verify quotient and remainder
Suppose the dividend is 121, the divisor is 11, the quotient is 10, and the remainder is 11.
Check the equation:
121 = 11 × 10 + 11
The equality holds, but the remainder is equal to the divisor. The required condition is r < b, not r ≤ b.
The correct representation is:
121 = 11 × 11 + 0
Therefore, the quotient is 11 and the remainder is 0.
### Example 8: Find a number from its quotient and remainder
A number divided by 6 gives a quotient of 12 and a remainder of 5. Find the number.
Using:
a = bq + r
Substitute the values:
a = 6 × 12 + 5
a = 72 + 5
a = 77
The number is 77.
Check the remainder condition:
0 ≤ 5 < 6
The representation is valid.
## 6. Euclid’s Division Lemma and the Euclidean Algorithm
One of the most important applications of Euclid’s Division Lemma is finding the Highest Common Factor (HCF), also called the Greatest Common Divisor (GCD), of two positive integers.
The Euclidean algorithm repeatedly applies division to replace a pair of numbers with a smaller pair until the remainder becomes zero.
The last non-zero remainder is the HCF.
### Why does the algorithm work?
Suppose:
a = bq + r
Every common divisor of a and b must also divide r, because:
r = a − bq
If a number divides both a and b, it divides bq and therefore divides a − bq.
Conversely, if a number divides both b and r, it divides bq + r, which equals a.
Therefore, a and b have exactly the same common divisors as b and r. Consequently:
HCF(a, b) = HCF(b, r)
This identity is the key principle behind the Euclidean algorithm.
### Example: Find the HCF of 135 and 225
Start by dividing the larger number by the smaller number.
225 = 135 × 1 + 90
Now divide 135 by 90:
135 = 90 × 1 + 45
Next, divide 90 by 45:
90 = 45 × 2 + 0
The remainder is now zero, so the last non-zero remainder is the HCF.
**HCF(135, 225) = 45**
### Example: Find the HCF of 867 and 255
Apply Euclid’s Division Lemma repeatedly.
867 = 255 × 3 + 102
255 = 102 × 2 + 51
102 = 51 × 2 + 0
The last non-zero remainder is 51.
Therefore:
**HCF(867, 255) = 51**
### Example: Find the HCF of 405 and 252
405 = 252 × 1 + 153
252 = 153 × 1 + 99
153 = 99 × 1 + 54
99 = 54 × 1 + 45
54 = 45 × 1 + 9
45 = 9 × 5 + 0
The last non-zero remainder is 9.
Therefore:
**HCF(405, 252) = 9**
These examples demonstrate how the lemma transforms a potentially difficult factorisation problem into a series of straightforward division steps.
## 7. Applications of Euclid’s Division Lemma
### Finding the Highest Common Factor
The most direct application is calculating the HCF of two positive integers. Instead of listing all factors of both numbers, the Euclidean algorithm uses repeated division.
This approach is especially efficient for large integers.
### Testing divisibility
If the remainder is zero when an integer is divided by another positive integer, the dividend is exactly divisible by the divisor.
For example:
84 = 7 × 12 + 0
Therefore, 84 is divisible by 7.
If a non-zero remainder occurs, the dividend is not exactly divisible by that divisor.
### Understanding integer structure
The equation a = bq + r expresses an integer as a multiple of another integer plus a remainder. This representation is useful when studying divisibility, modular arithmetic, and number patterns.
For example, every integer divided by 2 has a remainder of either 0 or 1. These two possibilities correspond to even and odd integers.
### Simplifying fractions
The Euclidean algorithm can find the HCF of the numerator and denominator of a fraction. Dividing both by their HCF reduces the fraction to its simplest form.
For example, simplify 84/126.
Using the Euclidean algorithm:
126 = 84 × 1 + 42
84 = 42 × 2 + 0
Therefore, the HCF is 42.
Divide the numerator and denominator by 42:
84/126 = 2/3
### Computer science and algorithms
The Euclidean algorithm is a classic example of an efficient mathematical algorithm. It can be implemented in programming languages to calculate the GCD of integers.
It is useful in number theory software, rational-number simplification, modular arithmetic, and certain cryptographic computations.
The underlying idea is that replacing a pair of integers with a smaller pair preserves their GCD.
### Solving number-theory problems
The lemma is frequently used to prove statements about divisibility and common factors. It provides a structured way to reduce an integer problem to a simpler one.
It also supports more advanced mathematical reasoning about congruences, integer equations, and divisibility properties.
## 8. Common Mistakes When Applying Euclid’s Division Lemma
### Mistake 1: Forgetting the remainder condition
A valid representation must satisfy both:
a = bq + r
and:
0 ≤ r < b
Checking only the equation is insufficient.
For example, 29 = 5 × 4 + 9 is numerically correct, but it is not a valid division representation because the remainder 9 is greater than the divisor 5.
The correct representation is:
29 = 5 × 5 + 4
### Mistake 2: Allowing a negative remainder
Under the standard lemma, the remainder must be non-negative.
A representation with a negative remainder does not meet the stated conditions, even if the arithmetic equality is correct.
### Mistake 3: Confusing quotient and remainder
The quotient tells us how many complete groups of the divisor fit into the dividend. The remainder tells us what is left after forming those groups.
For 38 divided by 6, the quotient is 6 and the remainder is 2.
### Mistake 4: Stopping the Euclidean algorithm too early
When finding the HCF, continue applying the division process until the remainder becomes zero. The HCF is the last non-zero remainder, not necessarily the first remainder.
### Mistake 5: Treating the lemma and the algorithm as identical
Euclid’s Division Lemma establishes the existence and uniqueness of the quotient and remainder. The Euclidean algorithm is a repeated application of division that uses the lemma to find the HCF.
They are related, but they are not the same statement.
### Mistake 6: Dividing by zero
The divisor b must be positive. Division by zero is undefined, so the lemma cannot be applied with b = 0.
### Mistake 7: Incorrect arithmetic
Small multiplication or subtraction errors can lead to an incorrect quotient or remainder. Always check the final representation by substituting the values into a = bq + r.
## 9. Practice Questions
Solve these questions to test your understanding.
1. Express 29 in the form 5q + r, where 0 ≤ r < 5.
2. Divide 74 by 9 and identify the quotient and remainder.
3. Write 144 in the form 11q + r.
4. Check whether 56 = 6 × 8 + 8 is a valid representation under the lemma.
5. Find the HCF of 96 and 36 using the Euclidean algorithm.
6. Find the HCF of 252 and 105.
7. A number divided by 8 gives a quotient of 15 and a remainder of 3. Find the number.
8. Explain why the remainder must be smaller than the divisor.
9. Find the HCF of 455 and 105.
10. State the mathematical formula of Euclid’s Division Lemma and explain each symbol.
### Answers
**1.** 29 = 5 × 5 + 4. The quotient is 5 and the remainder is 4.
**2.** 74 = 9 × 8 + 2. The quotient is 8 and the remainder is 2.
**3.** 144 = 11 × 13 + 1. The quotient is 13 and the remainder is 1.
**4.** No. Although 6 × 8 + 8 = 56, the remainder equals the divisor. The correct representation is 56 = 6 × 9 + 2.
**5.** 96 = 36 × 2 + 24; 36 = 24 × 1 + 12; 24 = 12 × 2 + 0. The HCF is 12.
**6.** 252 = 105 × 2 + 42; 105 = 42 × 2 + 21; 42 = 21 × 2 + 0. The HCF is 21.
**7.** a = 8 × 15 + 3 = 123. The number is 123.
**8.** If the remainder were equal to or greater than the divisor, another complete group of the divisor could be taken out. The quotient could be increased, producing a smaller valid remainder.
**9.** 455 = 105 × 4 + 35; 105 = 35 × 3 + 0. The HCF is 35.
**10.** The formula is a = bq + r, where a is the dividend, b is the positive divisor, q is the integer quotient, and r is the remainder satisfying 0 ≤ r < b.
## 10. Frequently Asked Questions
### What is Euclid’s Division Lemma?
Euclid’s Division Lemma states that for positive integers a and b, there exist unique integers q and r such that a = bq + r, with 0 ≤ r < b.
### What is the formula of Euclid’s Division Lemma?
The formula is a = bq + r. The remainder must be non-negative and strictly smaller than the positive divisor.
### What is the difference between Euclid’s Division Lemma and the Euclidean algorithm?
The lemma establishes that a valid quotient-and-remainder representation exists and is unique. The Euclidean algorithm repeatedly applies division to calculate the HCF of two positive integers.
### Why is Euclid’s Division Lemma important?
It provides the mathematical foundation for the Euclidean algorithm and supports the study of divisibility, common factors, and number theory.
### Can the remainder be zero?
Yes. A remainder of zero means that the dividend is exactly divisible by the divisor.
For example, 42 = 7 × 6 + 0.
### Can the remainder be equal to the divisor?
No. The condition is r < b. If the remainder equals the divisor, the quotient can be increased by one and the remainder becomes zero.
### How is the lemma used to find HCF?
The lemma expresses a = bq + r. Since HCF(a, b) = HCF(b, r), the process can be repeated until the remainder becomes zero. The last non-zero remainder is the HCF.
### Is the quotient always smaller than the dividend?
For positive integers a and b, the quotient depends on the values of both numbers. If a is smaller than b, the quotient is zero and the remainder is a. If a is at least b, the quotient is positive. Therefore, the quotient is not always strictly smaller than the dividend in every possible integer setting, although for positive a and b it is smaller than a whenever a ≥ b and b ≥ 1, except that the equality case a = b = 1 gives q = 1.
### Who was Euclid?
Euclid was an ancient Greek mathematician associated with the foundational mathematical text *Elements*. His work organised and developed many results in geometry and number theory. The division lemma and Euclidean algorithm are named in connection with the mathematical tradition associated with him.
### Is Euclid’s Division Lemma useful in higher mathematics?
Yes. The principle behind the lemma and its algorithm is used in number theory, modular arithmetic, algebra, and computer algorithms involving integer divisibility and greatest common divisors.
## Conclusion
Euclid’s Division Lemma is a foundational theorem that describes how a positive integer can be represented using another positive integer, a quotient, and a remainder.
Its formula is:
a = bq + r, where 0 ≤ r < b.
The proof establishes that the quotient and remainder both exist and are unique. The lemma also provides the foundation for the Euclidean algorithm, which finds the HCF of two positive integers through repeated division.
By learning the theorem statement, understanding the remainder condition, practising numerical examples, and applying the algorithm, students can develop a strong foundation in number theory. These ideas also support fraction simplification, divisibility tests, modular arithmetic, and computational methods.
A clear understanding of Euclid’s Division Lemma makes many number-theory problems easier to solve and prepares students for more advanced mathematical theorems.