Type-1 - Euclid's Division Lemma

The first mathematician who broad a new outlook for the study of geometry is Euclid. Euclid’s division lemma is a proven statement which is used to prove other statements in the branch of mathematics.

The basis of Euclidean division algorithm is Euclid’s division lemma. To calculate the Highest Common Factor (HCF) of two positive integers x and y, Euclid’s division algorithm is used. HCF also called as highest common factor is the largest number which exactly divides two or more positive integers. By dividing both the integers x and y the remainder is zero.

Definition:

Euclid’s Division Lemma states that, if two positive integers “a” and “b”, then there exists unique integers “q” and “r” such that which satisfies the condition a = bq + r where 0 ≤ r ≤ b.


General Form of Euclid’s Division Lemma,

 

Let us take an example of the division of positive integer by positive integer, say 58 by 9. 

In this example, 9 is the divisor, 58 is the dividend, 6 is the quotient and 4 is the remainder. 

We can write the result in following form by applying the Euclid’s Division Lemma method,

58 = 9 x 6 + 4; 0 ≤ 4 ≤ 9


Numerical Problem 1:

Let us consider a = 217, b = 5 be two integers. Divide 217 by 5 as below:

Solution:

From the given,

  • Divisor = 5
  • Dividend= 217

After division, Quotient = 43 and Remainder = 2 

If we apply the principle of Dividend = Divisor X Quotient +Remainder as per the Euclid’s Division Lemma method

We can write as, 217 = 5 X 43 +2.

Also the above equality holds good

Hence the Euclid’s Division Lemma is verified

 

Theorem Proof:

Given: 

Let q=⌊⌋ and r=a−bq. 


Where, 

  • q is the Quotient
  • r is the remainder
  • a is the Dividend
  • b is the divisor


By Euclid’s Division Lemma method, we know that a=bq+r. 


To prove:  

To show that 

Remainder obtained after two numbers should always be greater than 0 and less than the divisor i.e; 0≤ra−bq ≥ 0

Proof: 

If we multiply all members of the Inequality (1) by −b, which is a negative number, we get:

 ---------Inequality (2)

If we now add “a”, and substitute q in the lace of ⌊⌋ we get in the Inequality (2) we get,


b >a−bq ≥ 0


We know that r=a−bq which implies that 0≤rr1. Then


  • (bq1+r1)− (bq2 +r2) =a−a=0
  • ⇔b (q1−q2) + (r1−r2) =0
  • ⇔b (q1−q2) = (r2 −r1)


By definition of divisibility, 

b|r2−r1 and therefore b ≤ r2 −r1, 


As per our assumption b > r2 > r1 ≥ 0 we have a contradiction, and this tells us that r1=r2. 

Finally, we also have that b (q1 −q2) =0, and since we know that b≠0, we also conclude that q1=q2, and this completes the proof.