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,
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,
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
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.
To find the Highest Common Factor (HCF) of both the numbers 78 and 980.
Choose the largest integer first, i.e. 980
We know that as per the Euclid Division Lemma, a = bq + r where 0 ≤ r ≤ b;
980 = 78 × 12 + 44
Now here
Dividend, a = 980,
Divisor, b = 78,
Quotient, q = 12 and
Remainder, r = 44.
By considering the divisor as 78 and the remainder as 44 and applying the Euclid division method once again, we get
78 = 44 × 1 + 34
Similarly, consider the divisor as 44 and the remainder 34 and apply the Euclid division method again, we get
44 = 34 × 1 + 10
Following the same procedure again, till we reach on o the remainder as Zero
34 = 10 × 3 + 4 (Divisor = 34, Remainder = 10)
10=4×2+2 (Divisor = 10, Remainder = 4)
4=2×2+0
We got the reminder as 0. Hence we need to stop applying the Euclid division method further.
From observation of the last value we can conclude that 2 is the Highest common factor(HCF) of the two given numbers 980 and 78.