Euclid Division Lemma

Euclid's Division Lemma which is one of the fundamental theorems proposed by the ancient Greek mathematician Euclid which was used to prove various properties of integers. The Euclid's Division Lemma also serves as a base for Euclid's Division Algorithm which is used to find the GCD of any two numbers.

Euclid's Division Lemma gives the relation between the various components of Division. The statement of Euclid's Division Lemma is as follows:

Dividend = Divisor × Quotient + Remainder

Statement of Euclid's Division Lemma

For any two positive integers a and b, where a ≥ b there exists a unique set of integers q and r, such that: 

a = b q + r
Dividend = (Divisor × Quotient) + Remainder

Where, 

• q is called the quotient, and 
• r is called the remainder, 0 ≤ r < b.

• Euclid's Division Lemma has many Applications related to the Divisibility of Integers
• It can be used to find the HCF of two numbers.

Articles Related to Euclid's Division Lemma:

• HCF and LCM
• GCD by Long Division Method

Euclid’s Division Lemma Example

Let’s consider an example of Euclid’s Division Lemma for better understanding.

Here, the given numbers are, 39(=a) and 6(=b) we can write it in a = bq + r form as, 39 = 6×6 + 3

where, quotient(q) is 6 and remainder(r) is 3.

Proof Of Euclid Division Lemma

Consider the following arithmetic progression.

………, a − 3b, a − 2b, a − b, a, a + b, a + 2b, a + 3b, ……

The above arithmetic progression has a common difference ‘b′, and it extends indefinitely in both directions.
Now, Let's consider the smallest non-negative term of this arithmetic progression to be r.

The difference between the smallest non- negative term r and a will be in multiple of the common difference 'b' as they both are in A.P.

So we can write it as,

a – r = bq
a = bq + r

Where, r is the smallest non-negative integer satisfying the above result. 
Therefore, 0 ≤ r < b

Thus, we have a = bq + r, where 0 ≤ r < b

Now, to prove the Uniqueness of q and r:

Let's Consider another pair q′ and r′ such that a = bq′ + r′ and 0 ≤ r′<b, then we would have:

bq + r = bq′ + r′
b(q − q′) = r′ − r

Since 0≤r′<b and 0≤r<b,
then, ∣r′−r∣<b

Therefore, the only possible way for this equation to hold true is if q=q′ and r=r′.

Therefore it is proved that q and r are unique .

Thus, for every two numbers a and b we have unique value of q and r such that 'a = bq + r', as defined in the Euclid's Division Lemma.

Solved Examples on Euclid's Division Lemma

Example 1: Find the quotient and remainder when 315 is divided by 17 using Euclid's Division Algorithm.

Solution:

Given: Dividend = 315, Divisor = 17

Using Euclid's Division Lemma, Divide 315 by 17
⇒ 315 = 17 × 18 + 9

Thus, quotient is 18 and remainder is 9.

Example 2: Find the quotient and remainder when 73 is divided by 9 using Euclid's Division Algorithm.

Solution:

Given: Dividend = 73, Divisor = 9

Using Euclid's Division Lemma, Divide 73 by 9
⇒ 73 = 9 × 8 + 1

Therefore, when 73 is divided by 9, the quotient is 8 and the remainder is 1.

Next Article - Euclidean Algorithm

For Programmer: Euclidean Algorithms basic and extended