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  5 + 2.

We can thus write this rule about the dividend as

Dividend = Divisor  Quotient + Remainder

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.

If a and b are positive integers, then there exist integers q and r such that a = bq + r, where 0  r < b

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.

Board question(s) related to this lesson: