A day full of math games & activities. Find one near you.

Euclid's Division Lemma

Euclid's division lemma states that for any two positive integers, say 'a' and 'b', the condition 'a = bq +r', where 0 ≤ r < b always holds true. Mathematically, we can express this as 'Dividend = (Divisor × Quotient) + Remainder'. A lemma is a statement that is already proved. Euclid, a Greek mathematician, devised Euclid's division lemma.

1.	Euclid’s Division Lemma
2.	Euclid's Division Lemma Proof
3.	How To Find HCF By Euclid's Division Lemma?
4.	FAQs on Euclid's Division Lemma

Euclid’s Division Lemma

Euclid’s Division Lemma (lemma is similar to a theorem) says that, for given two positive integers, 'a' and 'b', there exist unique integers, 'q' and 'r', such that: a = bq+r, where 0 ≤r <b.

The integer 'q' is the quotient and the integer 'r' is the remainder. The quotient and the remainder are unique. In simple words, Euclid's division lemma statement is that if we divide an integer by another non-zero integer, we will get a unique integer as quotient and a unique integer as remainder.

We can write the above scenario mathematically as: 'Dividend = (Divisor × Quotient) + Remainder'. The above scenario shows the way of representing the division of positive integers with the help of Euclid's division lemma.

Here are some examples of the application of Euclid's division lemma:

23 = (2 × 11) + 1
54 = (7 × 7) + 5
63 = (9 × 7) + 0

Euclid’s Division Lemma Proof

Euclid’s lemma or Euclid's division lemma statement says that for given two positive integers, 'a' and 'b', there exists unique integers 'q' and 'r' such that, a = bq+r, 0 ≤ r <b.

So, let's take a = 9 and b = 1.

9 = (1 × 9) + 0

Here, q = 9 and r = 0, and we can clearly see that 0 ≤ r < 1.

Now, let's take a = 9 and b = 2.

9 = (2 × 4) + 1

Here, q = 4 and r = 1, and we can clearly see that 0 ≤ r < 2.

Now, let's take a = 9 and b = 3.

9 = (3 ×3 ) + 0

Here, q = 3 and r = 0, and we can clearly see that 0 ≤ r < 3.

Now, let's take a = 9 and b = 4.

9 = (4 × 2) + 1

Here, q = 2 and r = 1, and we can clearly see that 0 ≤ r < 4.

We can observe that when we divide two integers using the Euclid division lemma, we always get a non-negative integral remainder less than the divisor.

How to Find HCF By Euclid's Division Lemma?

Euclid's division lemma has many uses or applications. Let's learn about two of the most important uses of this algorithm. We use Euclid's division lemma to find the HCF of large numbers which is typically difficult to calculate using basic HCF calculation techniques. The HCF of two numbers can be calculated with the help of Euclid's division lemma by following these steps.

Let's take two numbers 'c' and 'd' for which we need to find the HCF such that c > d.

Step 1:- Apply Euclid’s division lemma to 'c' and 'd'. We can find whole numbers, 'q' and 'r' such that c = dq + r, 0 ≤ r < d.
Step 2:- If r = 0, 'd' is the HCF of 'c' and 'd'. If r ≠ 0, apply the division lemma again to 'd' and 'r'.
Step 3:- Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

Let us use Euclid’s division lemma to find the HCF of 42 and 64. The solution is shown in the figure below.

HCF Using Euclid's Division Lemma

Since the remainder is now zero, we can stop the process. The HCF of 42 and 64 is 2. When we apply Euclid's division lemma repeatedly to find the HCF, this process is known as Euclid's division algorithm.

Euclid's Division Lemma and Properties of Numbers

We can understand the various properties of odd and even numbers using Euclid's division lemma. For example, let us show that every positive even integer is of the form 2q and that every positive odd integer is of the form 2q + 1, where q is some integer. Assume a is a positive integer and b = 2.

By Euclid’s division lemma, we can write:

a = 2q + r

where q ≥ 0 and r can take either 0 or 1 by the rule 0 ≤ r < b.

Thus, a = 2q or a = 2q + 1.

If 'a' is of the form '2q', then 'a' is an even integer, and if 'a' is of the form 2q + 1, then it is an odd integer.

For example, if we substitute q = 1, 2, and 3, then a = 2q is even.

a = 2 × 1 = 2
a = 2 × 2 = 4
a = 2 × 3 = 6

And, if we substitute q = 1, 2, and 3, we will find that a = 2q + 1 is odd.

a = (2 × 1) + 1 = 3
a = (2 × 2) + 1 = 5
a = (2 × 3) + 1 = 7

Important Notes

Here are a few important points to remember about Euclid's division lemma.

When you divide one integer by another non-zero integer, you are left with a quotient and a remainder.
The remainder is always less than the divisor.
Euclid's lemma is used to calculate the HCF of large numbers.

Related Topics

Here are some interesting topics related to Euclid's division lemma.

Euclid's Division Lemma Examples

Example 1: Given that 'n' is an odd integer. Using Euclid's division lemma, prove that n² - 1 is a multiple of 8.

Solution:

By Euclid’s division lemma, 'n' can be written as:

n = 2k+1, k ∈ Z (since n is an odd integer)

Thus, n²−1 = (2k+1)²−1
= (4k²+4k+1) − 1
= 4k²+4k
= 4k(k+1)

Note that the product k(k+1) will always be even. This is because either 'k' is even, or 'k + 1' is even, and the product of any number with an even number is always even. Thus, 4k(k + 1) must be a multiple of 8. Therefore, n² - 1 is a multiple of 8.
Example 2: Using Euclid's division lemma, find the HCF of 420 and 130.

Solution:

Given:

Let's apply Euclid's division lemma to calculate the HCF of these numbers.
As per Euclid's Division Lemma, c = dq + r, 0 ≤ r < d. Since 420 > 130, here, c = 420 and d = 130.

420 = (130 × 3) +30
130 = (30 × 4) +10
30 = (10 × 3) + 0

Therefore, the HCF of 420 and 130 is 10.
Example 3: The cube of a positive integer is divided by 9. Using Euclid's division lemma, find what can be the possible remainders?

Solution:

We have to use Euclid's division lemma to find the remainders. If we can express the cube of any positive integer in the form 9q + r, then we can solve the problem easily. We will then have to find what values r can take.

Let 'n' be any positive integer.

Note that when we divide 'n' by 3, we can get three possible remainders: 0, 1, or 2.

Thus, 'n' can be written as:
n=3k or n=3k+1 or n=3k+2

Let's consider each case separately.

Case 1: In this case, we have:

n³ = (3k)³
= 27k³
= 9(3k³)

Thus, the cube of 'n' will be perfectly divisible by 9 in this case (the remainder will be 0).

Case 2: In this case, we have:
n³=(3k+1)³
=(3k)³+(1)³+3(3k)(1)(3k+1)
=27k³+1+9k(3k+1)
=9k(3k²+3k+1)+1
=9{k(3k²+3k+1)}+1

It is clear that on dividing the cube of 'n' by 9, in this case, we will be left with a remainder of 1.

Case 3: In this case, we have:

n³=(3k+2)³
=(3k)³+(2)³+3(3k)(2)(3k+2)
=27k³+8+18k(3k+2)
=9k(3k²+6k+4)+8
=9{k(3k²+6k+4)}+8

In this case, on dividing the cube of n by 9, we will be left with a remainder of 8.

Thus, we conclude that dividing the cube of a positive integer by 9 can yield three possible remainders which are 0, 1, and 8.

In other words, the cube of any integer can be expressed as follows:

n³ = 9k or n³ = 9k + 1 or n³ = 9k + 8

You can verify this result by taking some cubes and checking the remainders you obtain upon their division by 9. Therefore, possible remainders are 0, 1, 8.

go to slide go to slide go to slide

Have questions on basic mathematical concepts?

Become a problem-solving champ using logic, not rules. Learn the why behind math with our certified experts

Book a Free Trial Class

Practice Questions on Euclid's Division Lemma

go to slide go to slide go to slide

FAQs on Euclid's Division Lemma

What is Euclid's Division Lemma?

A lemma is a proven statement that is used to prove another statement. As per Euclid's division lemma, for any two positive integers, say 'a' and 'b'. the condition 'a = bq +r' , where 0 ≤ r < b. always holds true. Mathematically we can represent it as 'Dividend = (Divisor × Quotient) + Remainder. For example, 59 = (7 × 8) + 3.

What is Euclid's Division Lemma Formula?

a = bq + r, 0 ≤ r < b, where 'a' and 'b' are two positive integers, and 'q' and 'r' are two unique integers such that a = bq + r holds true. This is the formula for Euclid's division lemma.

How to Find HCF Using Euclid's Division Lemma?

Euclid's division lemma is used to find the HCF of two large numbers by using the following statement 'a = bq +r' , where 0 ≤ r < b. Here 'a' and 'b' are positive integers and a > b. To find the HCF of two numbers c and d, follow the steps given below.

Apply Euclid’s division lemma to 'c' and 'd'. We can find whole numbers, 'q' and 'r' such that c = dq + r, 0 ≤ r < d. If r = 0, 'd' is the HCF of 'c' and 'd'. If r ≠ 0, apply the division lemma to 'd' and 'r'. Repeat the process until the remainder is zero. The divisor at this stage will be the required HCF.

Use Euclid's Division Lemma to Find the HCF of 867 and 225.

As per the Euclid's Division Lemma, 'a = bq +r' , where 0 ≤ r < b. Here, a = 867 and b = 225. Therefore, 867 = (225 × 3) + 192. We repeat the same process until the value of the remainder 'r' becomes 0. Let us repeat the same step again with a = 225 and b = 192. Therefore, 225 = (192 × 1) + 33. Now repeat the same step with a = 192 and b = 33. Therefore, 192 = (33 × 5) + 27. Now repeat the same step with a = 33 and b = 27. 33 = (27 × 1) + 6. Now, a = 27 and b = 6. Therefore, 27 = (6 × 4) + 3. Now, a = 6 and b = 3. Therefore, 6 = (3 × 2) + 0. Since the remainder is 0, we stop here. In the previous step we have the remainder as 3. Therefore, the HCF of 867 and 225 is 3.

What are the Applications of Euclid's Division Lemma?

Euclid's division lemma has the following applications. They are,

To find the properties of numbers. For example, we can show that every positive even number is of the form '2q' and every positive odd number is of the form '2q +1'.
To find the HCF of two large numbers.

Download FREE Study Materials

Download Arithmetic Integers Worksheets

Euclid's Division Lemma Worksheets

Math worksheets and
visual curriculum