1.Euclid's division lemma

​ Chapter 1: Real Numbers

Euclids Division Lemma

What is a dividend? Let us understand it with the help of a simple example. Can you divide 14 by 6?

​

After division, we get 2 as the quotient and 2 as the remainder.

Thus, we can also write 14 as 6 × 2 + 2.

A dividend can thus be written as:

Dividend = Divisor × Quotient + Remainder

Can you think of any other number which, when multiplied with 6, gives 14 as the dividend and 2 as the remainder?

Let us try it out with some other sets of dividends and divisors.

(1) Divide 100 by 20: 100 = 20 × 5 + 0

(2) Divide 117 by 15: 117 = 15 × 7 + 12

(3) Divide 67 by 17: 67 = 17 × 3 + 16

Thus, if we have a dividend and a divisor, then there will be a unique pair of a quotient and a remainder that will fit into the above equation.

This brings us to Euclid’s division lemma.

If a and b are positive integers, then there exist two unique integers, q and r,
such that a = bq + r
This lemma is very useful for finding the H.C.F. of large numbers where breaking them into factors is difficult. This method is known as Euclid’s Division Algorithm.

Let us look at some more examples.

Example 1: Find the H.C.F. of 4032 and 262 using Euclid’s division algorithm.

Solution:

Step 1:

First, apply Euclid’s division lemma on 4032 and 262.

4032 = 262 × 15 + 102

Step 2:

As the remainder is non-zero, we apply Euclid’s division lemma on 262 and 102.

262 = 102 × 2 + 58

Step 3:

Apply Euclid’s division lemma on 102 and 58.

102 = 58 × 1 + 44

Step 4:

Apply Euclid’s division lemma on 58 and 44.

58 = 44 × 1 + 14

Step 5:

Apply Euclid’s division lemma on 44 and 14.

44 = 14 × 3 + 2

Step 6:

Apply Euclid’s division lemma on 14 and 2.

14 = 2 × 7 + 0

In the problem given above, to obtain 0 as the remainder, the divisor has to be taken as 2. Hence, 2 is the H.C.F. of 4032 and 262.

Note that Euclid’s division algorithm can be applied to polynomials also.

Example 2: A rectangular garden of dimensions 190 m × 60 m is to be divided in square blocks to plant different flowers in each block. Into how many blocks can this garden be divided so that no land is wasted?

Solution:

If we do not want to waste any land, we need to find the largest number that completely divides both 190 and 60 and gives the remainder 0, i.e., the H.C.F. of (190, 60).

To find the H.C.F., let us apply Euclid’s algorithm.

190 = 60 × 3 + 10

60 = 10 × 6 + 0

Therefore, the H.C.F. of 190 and 60 is 10.

Therefore, there will be​= 19 square blocks along the length of the garden and ​= 6 blocks along its breadth.

Hence, the total number of blocks in the garden will be 19 × 6 = 114.

Example 3: Find the H.C.F. of 336 and 90 using Euclid’s division algorithm.

Solution:

As 336 > 90, we apply the division lemma to 336 and 90.

336 = 90 × 3 + 66

Applying Euclid’s division lemma to 90 and 66: 90 = 66 × 1 + 24

Applying Euclid’s division lemma to 66 and 24:

66 = 24 × 2 + 18

Applying Euclid’s division lemma to 24 and 18:

24 = 18 × 1 + 6

Applying Euclid’s division lemma to 18 and 6:

18 = 6 × 3 + 0

As the remainder is zero, we need not apply Euclid’s division lemma anymore. The divisor (6) is the required H.C.F.

Example 4: Find the H.C.F. of 45, 81, and 117 using Euclid’s division algorithm.

Solution:

Let us begin by choosing any two out of the three given numbers, say 45 and 81. As 81 > 45, we apply Euclid’s division lemma to 81 and 45.

81 = 45 × 1 + 36

Applying Euclid’s division lemma to 45 and 36:

45 = 36 × 1 + 9

Applying Euclid’s division lemma to 36 and 9:

36 = 9 × 4 + 0

As the remainder is zero, the H.C.F. of 45 and 81 is 9.

Now, we again need to apply Euclid’s division algorithm on the H.C.F. of the two numbers and the remaining number.

Since the H.C.F. of 45 and 81 is 9 and the third number is 117, we apply Euclid’s division lemma to 117 and 9.

117 = 9 × 13 + 0

As the remainder is zero, the H.C.F. of 9 and 117 is 9.

Here, the second H.C.F. (the H.C.F. of the H.C.F. of the first two numbers and the third number) is the H.C.F. of the three numbers.

Thus, we can say that the H.C.F. of the three numbers is 9.

Example 5: In an inter-school essay writing competition, the numbers of participants from schools A, B, and C are 20, 16, and 28 respectively. If the participants in each room are from the same school, then find the minimum number of rooms required such that each room has the same number of participants.

Solution:

If we need to find the minimum number of rooms, then we need to keep the maximum number of participants in each room i.e., we need to find the largest number that completely divides 20, 16, and 28.

Thus, we start by choosing any two out of the given three numbers, say 20 and 16. Applying Euclid’s division lemma to 20 and 16:

20 = 16 × 1 + 4

Applying Euclid’s division lemma to 16 and 4:

16 = 4 × 4 + 0

Hence, 4 is the H.C.F. of 20 and 16.

Applying Euclid’s division algorithm to 28 and 4:

28 = 4 × 7 + 0

Hence, 4 is the H.C.F. of 28 and 4.

∴H.C.F. of 20, 16, 28 = 4

Therefore, each room would have 4 participants.

The number of rooms in which the participants from schools A, B, and C can be

accommodated is ​ = 5,​ = 4, and ​= 7 respectively.

Therefore, a total of 5 + 4 + 7 =16 rooms are required.

The Use Of Euclids Division Lemma To Prove Mathematical Relationships

​Whenever we divide 32 by 5, we will get 6 as the quotient and 2 as the remainder. Therefore, we can also write 32 as 6 x 5 + 2.

We can thus write this rule about the dividend as

 

This expression is unique, i.e., whenever we divide an integer (dividend) by another integer (divisor), we always get a fixed quotient and a fixed remainder.

The above statement can be proven by taking an example.

Whenever we divide 54 by 11, we will get 4 as the quotient and 10 as the remainder. We will never get a quotient other than 4 and a remainder other than 10 when we divide 54 by 11.

This brings us to Euclid’s division lemma.

​

This lemma has several applications, one of which is to prove mathematical relationships among numbers.

Let us discuss this concept with the help of a few examples.

Example 1: Prove that every positive integer is of the form 3p, 3p + 1, or 3p + 2, where p is any integer.

Solution:

Let a be any positive integer and let b = 3.

Applying Euclid’s algorithm to a and 3:

a = 3p + r; for some integer p and 0 ≤ r < 3

Therefore, a can be 3p, 3p + 1, or 3p + 2.

As a is a positive integer, we can say that any positive integer is of the form 3p, 3p + 1, or 3p + 2.

Example 2: Prove that every positive even integer is of the form 2m and every positive odd integer is of the form 2m + 1, where m is any integer.

Solution:

Let a be any positive integer and let b = 2.

According to Euclid’s division lemma, there exist two unique integers m and r such that

a = bm + r = 2m + r, where 0 ≤ r < 2. Thus, r = 0 or 1

If r = 0, i.e., if a = 2m, then the expression is divisible by 2. Thus, it is an even number.

If r = 1, i.e., if a = 2m + 1, then the expression is not divisible by 2. Thus, it is an odd number.

Thus, every positive even integer is of the form 2m and every positive odd integer is of the form 2m + 1.

Example 3: Prove that the expression y(y + 1) always represents an even number, where y is any positive integer.

Solution:

Let y be an integer. Thus, it may be either odd or even.

When y is an odd number, i.e., when y is of the form 2p + 1, where p is an integer:

y(y + 1) = (2p + 1)(2p + 1 + 1) = (2p + 1)(2p + 2) = 2(2p + 1)(p + 1)

The above expression is a multiple of 2. Thus, the expression y(y + 1) represents an even number.

When y is an even number, i.e., when y is of the form 2q, where q is an integer:

y(y + 1) = (2q)(2q + 1) = 2q(2q + 1)

The above expression is a multiple of 2. Thus, the expression y(y + 1) represents an even number.

Thus, for a positive integer y, the expression y(y + 1) always represents an even number.

Example 4:

Show that

(a)    The sum, the difference, and the product of two even numbers is always even.

(b)    The sum and the difference of two odd numbers is always even, whereas their product is always odd.

Solution:

(a)  Let there be two even numbers, x and y, such that x = 2m and y = 2n, where m and n are two positive integers.

Now, x + y = 2m + 2n = 2(m + n) = 2p, where p = m + n is an integer. Thus, x + y is always even.

Similarly, x − y = 2m − 2n = 2(m − n) = 2q, where q = m − n is an integer. Thus, x − y is always even.

Likewise, xy = 2m × 2n = 4mn = 2(2mn) = 2t, where t = 2mn is an integer. Thus, xy is always even.

Hence, the sum, the difference, and the product of two even numbers is always even.

(b) Let there be two odd numbers x and y such that x = 2m + 1 and y = 2n + 1, where m and n are two positive integers.

Now, x + y = (2m + 1) + (2n + 1) = 2(m + n + 1) = 2p, where p = m + n + 1 is an integer. Thus, x + y is even.

Similarly, x − y = (2m + 1) − (2n + 1) = 2(m − n) = 2q, where q = m − n is an integer.

Thus, x − y is even.

Likewise, xy = (2m + 1)(2n + 1) = 2(2mn + m + n) + 1 = 2t + 1, where t = 2mn + m + n is an integer.

Thus, xy is always odd.

Hence, the sum and the difference of two odd numbers is always even, whereas their product is always odd.