Class 10 Maths- Euclids Division Lemma

You must know

Division – Division is splitting something (or a number) into equal parts or groups. It is the result of ‘fair sharing’.

• The number to be divided is known as the dividend

• The number, which divides the other number, is known as the divisor

Factor – The factor of a number is a whole number, which divides the number exactly into a whole number, leaving no remainder. For example, 13 is a factor of 52 because 13 divides 52 without leaving any remainder (52 ÷ 13 = 4 leaving no remainder).

HCF – The Highest Common* Factor (HCF) of a set of numbers is the highest (largest) of the common factors of the numbers.

*The word common suggests that HCF must be about ‘something’ common between at least two numbers. And that ‘something’ is actually the common factor among the set of numbers.

In other words, the HCF of two (or more) numbers is the highest (largest) number that divides two numbers without leaving any remainder.

The common factors of 12 and 18 are 1, 2, 3 and 6.

The highest (largest) common factor is 6, so it’s the HCF of 12 and 18.

Getting started

At the outset, it’s very important to make a confession and then move on.

Surprising as it may sound, our experience in teaching math dictates that the Euclid’s lemma becomes far easier to understand if we understand the meaning of the word ‘lemma’. A lemma is a proven statement, typically named a lemma to distinguish it as a truth, used as a stepping stone to a larger result rather than an important statement in and of itself. Essentially, what needs to be understood is that Euclid’s lemma is not a big mathematical discovery by itself but it’s a very fundamental and handy piece of knowledge. Knowledge of Euclid’s lemma is a great help in many mathematical operations.

What’s the fundamental feature of Euclid’s lemma? It captures a fundamental property of prime numbers: If a prime divides the product of two numbers, it must divide at least one of those numbers. For example, since 133 × 143 = 19019 is divisible by 19, one or both of 133 or 143 must as well be divisible by 19. In fact, 133 is divisible by 19 (19 × 7 = 133).

In more general terms, if ‘n x m’ has a prime factor, it had to come from either ‘n’ or ‘m’. That means the prime factor divides ‘n’ or it divides ‘m’. You can’t get a piece of the prime from ‘n’ and another piece from ‘m’. That’s the power of prime numbers - they can’t be broken down further. Euclid’s lemma captured this unique power of prime numbers as the building blocks of integers.

The lemma property doesn’t apply to composite numbers. For example, 6 divides 10 × 15 = 150 (150 = 6 × 25), but 6 doesn’t divide 10 or 15. 6 = 2 × 3, and 2 divides 10, and 3 divides 15, so 6 = 2 × 3 goes into the product, but not into either 10 or 15. 6 has two prime factors, so they can be split up.

This Euclid’s lemma is utilised by an algorithm known as ‘The Euclid’s division algorithm’. If you want to find the highest common factor (HCF) between two positive integers, you can use the Euclid’s division lemma to arrive at the HCF. Have you heard of the word algorithm? It is a term, which is used in mathematics and in computer science. Do you know what it means?

An algorithm is a series of well-defined step-by-step or procedures for solving problems and for making calculations.

Exploring Euclid division Lemma and algorithm

Let us now look at Euclid’s division algorithm with the following example. Consider the two positive integers 140 and 40. Can you find the HCF of these two numbers 140 and 40? An algorithm known as the Euclid’s division algorithm can be used to find the HCF of 140 and 40.

Divide 140, which is the larger integer, by 40:

140 divided by 40 is 3 with the remainder 20.

Using Euclid’s division lemma, we find that:

140 = (40 × 3) + 20

Now, take the divisor 40 and the remainder 20 and divide 40 by 20.

40 divided by 20 is 2 with the remainder 0.

Applying Euclid’s division lemma, we find that:

40 = (20 × 2) + 0.

Hence, the HCF of 140 and 40 is the divisor 20 as we cannot proceed further as the remainder has become 0.

The Euclid’s division algorithm is, thus, a series of steps, which can be used to find the highest common factor between two positive integers ‘c’ and ‘d’ with c > d by applying Euclid’s division lemma.

The steps of Euclid’s division algorithm with the example problem solved in brackets are as follows:

Step 1: Divide ‘c’ by’ d’ and apply Euclid’s division lemma to get two whole numbers, the quotient and remainder as ‘q’ and ‘r’ respectively.

c = dq + r, d > r ≥ 0

(In the example above, 140 = (40 × 3) + 20, 40 > 20 ≥ 0)

Step 2: If r = 0, then the divisor ‘d’ is the HCF of ‘c’ and ‘d’. If r is not equal to 0, then apply Euclid’s division lemma to the divisor ‘d’ and the remainder ‘r’.

(In the example above, r = 20, which is not equal to 0, and the divisor obtained is 40).

Applying Euclid’s division lemma, we get:

40 = (20 × 2) + 0

Step 3: The process is continued until the remainder is 0. The divisor obtained by repeating the process until the remainder is 0 is the HCF of the two positive integers ‘c’ and ‘d’.

(In the example given above, the divisor of 20 is obtained with a remainder of 0, so the process need not be continued. The divisor 20 thus obtained is the HCF of 140 and 40).

Euclid’s division Lemma: Let ‘a’ and ‘b’ be any two positive integers. Then, there exist unique integers ‘q’ and ‘r’ such that

a = bq + r, 0 ≤ r < b

If  = q, then r = 0. Otherwise, ‘r’ satisfies the stronger inequality 0 < r < b.

Euclid’s division algorithm: If ‘a’ and ‘b’ are positive integers such that a = bq + r, then every common divisor of ‘a’ and ‘b’ is a common divisor of ‘b’ and ‘r’, and vice-versa. The division lemma of Euclid assures us that each result obtained at every step of the division algorithm is absolutely the correct unique value for every possible dividend-divisor pair.

Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers ‘a’ and ‘b’ is the largest positive integer ‘d’ that divides both ‘a’ and ‘b’.

Suppose we need to find the HCF of the integers 455 and 42. We start with the larger integer, that is, 455. Then we use Euclid’s lemma to get:

455 = 42 × 10 + 35

Now consider the divisor 42 and the remainder 35, and apply the division lemma to get

42 = 35 × 1 + 7

Now consider the divisor 35 and the remainder 7, and apply the division lemma to get

35 = 7 × 5 + 0

Notice that the remainder has become zero, and we cannot proceed any further.

We claim that the HCF of 455 and 42 is the divisor at this stage, i.e., 7. You can easily verify this by listing all the factors of 455 and 42.

Example: Find the HCF of 65 and 117 and express it in the form 65 m + 117 n.

Solution: Given integers are 65 and 117 such that 117 > 65.

Applying division lemma to 65 and 117, we get
117 = 65 x 1 + 52 ……(i)	Here we divide c by d and apply Euclid’s division lemma to get two whole numbers, the quotient and remainder ‘q’ and ‘r’. c = dq + r, d > r ≥ 0
Since, the remainder 52 ≠ 0. So, we apply the division lemma to the divisor 65 and the remainder 52 to get
65 = 53 x 1 + 13 …..(ii)	If r = 0, then the divisor ‘d’ is the HCF of ‘c’ and ‘d’. If r is not equal to 0, then apply the Euclid’s division lemma to the divisor ‘d’ and the remainder ‘r’. So, applying Euclid’s division lemma again
We consider the new divisor 52 and the new remainder 13 and apply division lemma, to get
52 = 13 x 4 + 0
At this stage, the remainder is zero. So, the last divisor or the non-zero remainder at the earlier stage, i.e., 13, is the HCF of 65 and 117.
From (ii) we have
13 = 65 – 52 x 1	As seen above
13 = 65 – (117 + 65 x 1)	As seen above
13 = 65 – 117 + 65 x 1	Opening the bracket on RHS
13 = 65 x 2 + 117 x (–1)	We rearrange the RHS as we are required to express it in the form 65 m + 117 n
13 = 65 – 117 + 65 x 1
13 = 65 m + 117 n, where m = 2 and n = –1

To summarise, knowledge of Euclid’s lemma is a great help in many mathematical operations. It is utilised by an algorithm known as ‘The Euclid’s division algorithm’, which is used to find the highest common factor (HCF) between two positive integers. It's based on the properties of prime numbers that they are indivisible.