Collegedunia Team Content Curator
Content Curator
Euclid’s Division Lemma is proven to be used for the verification of other mathematical equations. It is also used for the division of integers. Euclid’s Division Lemma states that for a & b (two positive integers), integers q and r also exist and we get a = b q + r in where 0 ≤ r ≤ b. This principle was proven by the famous Greek mathematician Euclid who was also known as the father of geometry.
What is Euclid’s Division Lemma
Euclid’s Division Algorithm is also based on Euclid’s Lemma. If we consider two positive integers and two unique integers like q and r. Then,
a= b q + r,
Where, 0 <= r < b
Euclid’s Division Lemma is based on the Euclidean division algorithm. The Highest Common Factor (HCF) of two positive integers (a and b) is calculated using Euclid’s Division Algorithm. HCF is obtained by dividing two integers ‘a’ and ‘b’ and the remainder we get is zero.
Also Read:
Euclid’s Division Lemma Proof
Lemma’s theorem is a = b q +r, 0 <= r
Example 1: If we take a = 9 and b = 1
Using the theorem,
→ 9 = (1 x 9) + 0
So,
q = 9 &
r = 0,
so clearly 0 <= r < 1
Example 2: If we substitute, a = 9 and b = 2
Then,
9 = (2 x 4) + 1
Then,
q = 4 &
r = 1,
so clearly 0 <= r <2
Case 1: If we take q = 9 & b = 3
Then,
9 = (3 x 3) + 0
Here, q = 3 and r = 0 and we see that 0 <= r <3
Case 2: If we take q = 9 & b = 4
Then,
9 = (4 x 2) + 1
Here,
q = 2 and
r = 1 and we see that 0 <= r < 4
So, we see that we can always divide two integers by using Euclid’s division lemma and get a non-negative integral remainder which is less than the divisor.
Euclid’s Division Algorithm
For ‘a’ and ‘b’ (two positive integers) we know that a = b q +r, then for every common divisor of integers ‘a’ and ‘b’ has a common divisor of ‘b’ and ‘r’ and vice versa.
Mathematically it can be explained as
Dividend = (Quotient + Divisor) + Remainder
Lemma’s Statement states that if an integer is divided by another non-zero integer, a unique integer is obtained as a quotient and another integer as remainder.
Finding HCF Using Euclid’s Division Lemma
Consider two positive numbers 418 and 33 and we have to find the HCF of these two numbers.
Step 1: The larger integer which is 418 is taken and using Euclid’s Division Lemma, a = b q +r we get,
→ 418 = 33 x 12 + 22
Where
a = 418; b = 33; q = 12; r = 22
Step 2: Now if the divisor is 33 represented as ‘a’ and 22 as ‘b’, on applying Euclid’s Division Algorithm, we get
→ 33 = 22 x 1 + 11
Step 3: Again if we take 22 as divisor ‘a’ and 11 as ‘b’ and we apply Euclid’s Division Algorithm, we get
→ 22 = 11 x 2 + 0
Step 4: The remainder we obtain is 0 and thus we cannot do the process further.
The last divisor that is obtained is 11 and the HCF we get off 418 and 33 is 11.
Applications of Euclid’s Division Lemma
- Used for the division of the integers.
- Used in Euclid’s Division Algorithm as a key concept.
- Used for finding the HCF of the positive numbers.
- Used to find properties like odd numbers, even numbers, cube numbers, square numbers, etc.
Also Read:
| Determinant of a Matrix | Sin 30 Degrees |
| Sin 180 Degrees | Tan 0 Degrees |
| Quadrilateral Angle Sum Property | Sum of Squares |
Things to Remember
- If one integer is divided by a non-zero integer, we get a remainder and a quotient
- The remainder obtained is less than the divisor
- Euclid’s Division Lemma states that a= b q +r, where the condition 0≤ r < b should be satisfied.
- HCF of large numbers is calculated using Euclid’s Lemma.
Sample Question
Ques. Find the HCF (865, 255) using Euclid’s division lemma. (CBSE 2013) (2 marks)
Ans. 865 > 255
865 = 255 × 3 + 100
255 = 100 × 2 + 55
100 = 55 × 1 + 45
55 = 45 × 1 + 10
45 = 10 × 4 + 5
10 = 5 × 2 + 0
The remainder is 0.
HCF = 5
Ques. Find the largest number which divides 70 and 125 leaving the remainder 5 and 8 respectively. (CBSE 2015) (2 marks)
Ans. It is given that on dividing 70 by the required number, there is a remainder 5.
This means that 70 – 5 = 65 is exactly divisible by the required number.
Similarly, 125 – 8 = 117 is also exactly divisible by the required number.
65 = 5 × 13
117 = 3 x 3 × 13
HCF = 13
Required number = 13
Ques. By using Euclid’s algorithm, find the largest number which divides 650 and 1170. (CBSE 2017) (2 marks)
Ans. Given numbers are 650 and 1170.
1170 > 650
1170 = 650 × 1 + 520
650 = 520 × 1 + 130
520 = 130 × 4 + 0
HCF = 130
The required largest number is 130.
Ques. Find the HCF of 255 and 867 by Euclid’s division algorithm. (CBSE 2014) (2 marks)
Ans. 867 is greater than 255. We apply the division lemma to 867 and 255, to get
867 = 255 × 3 + 102
We continue the process till the remainder is zero
255 = 102 × 2 + 51
102 = 51 × 2 + 0, the remainder is zero.
HCF = 51
Ques. Show that any odd positive integer is of 4q+1 or 4q+3, in which q is some integer. (3 marks)
Ans. If we take ‘a’ where ‘a’ is the positive odd integer & we apply the Euclid’s division algorithm with b = 4.
So, 0 <= r < 4, the remainders we get are 0, 1, 2 and 3.
So a might be 4q, or 4q+1 or 4q+2 or 4q+3 in which q is the quotient. As, ‘a’ is odd, a will not be 4q or 4q+2 (as they are both divisible by 2)
Hence, the odd integer is in the form 4q+1 or 4q+3.
Ques. Using Euclid’s division algorithm, find HCF of numbers 675 and 81. (3 marks)
Ans. Taking the larger number 675 and using Euclid’s division algorithm, a = b q +r we get, 0<=r < b
675 = 81 x 8 + 27
Here, a = 675 and b = 81
By again applying Euclid’s division algorithm, we get
81 = 27 x 3 + 0
We cannot use it further as the remainder is zero. So, the divisor is 27. So, the HCF of 81 and 675 is 27.
Ques. Find HCF of numbers 135 and 225, using Euclid’s division algorithm. (2 marks)
Ans. So the given positive numbers are 225 and 135 and taking the greater number and applying Euclid’s Division Lemma, we get
225 = 135 x 1 + 90
Now if we take the divisor 135 and 90 as the remainder, we further get
135 = 90 x 1 + 45
Taking the divisor 90 and remainder 45 and again applying the theorem, we get
90 = 45 x 2 +0
As it is not further possible to apply the theorem as the remainder obtained is 0, the HCF of 135 and 225 is 45.
Ques. State the difference between Euclid’s Division Algorithm and Euclid’s Division Lemma. (2 marks)
Ans. The algorithm is used for well-defined steps for solving the problems, the word Lemma is known to be a proven statement which is used for proving other statements.
Euclid’s Division Lemma is used for proving the other theorems whereas Euclid’s Division Algorithm is used for finding the HCF of the two positive numbers by using Euclid’s Division Lemma.
Ques. Find the HCF of the two numbers 616 and 32, using Euclid’s Division Lemma. (2 marks)
Ans. So here the two positive numbers are 616 and 32. Using the theorem,
616 = 32 x 19 + 8
We get 8 as a remainder and 19 as a divisor, 8≠0. So, we can further apply Euclid’s Division Lemma
32 = 8 x 4 + 0
As 0 is obtained as remainder. Hence, the HCF of the two numbers 616 and 32 is 8.
Ques. Use Euclid’s Division Algorithm to find the HCF of: (3 marks)
(i) 196 and 38220
(ii) 867 and 255
Ans.
(i) By Euclid’s Division Algorithm, we have
38220 = 196 x 195 + 0
196 = 196 x 1 + 0
HCF (38220, 196) = 196
(ii) By Euclid’s Division Algorithm, we have
867 = 255 x 3 +102
255 = 102 x 2 + 51
102 = 51 x2 +0
HCF (887, 255) =51
Ques. Show that any positive odd integer is of the form 6q + 1, or 6q + 3, or 6q + 5, where q is some integer. (2 marks)
Ans. Let a be a positive odd integer. Also, let q be the quotient and r the remainder after dividing a by 6.
Then, a = 6q + r, where 0 <= r < 6
Putting r = 0, 1, 2, 3, 4 and 5, we get,
a = 6q, a =6q +1, a= 6q +2, a= 6q +3, a= 6q+4, a= 6q +5
But a = 6q, a = 6q+2 and a= 6q +4 are even.
Hence , when a is odd, it is of the form 6q+1, 6q+3 and 61+5 for some integer q.
Hence proved.
Ques. If the HCF of 408 and 1032 is expressible in the form 1032 × 2 + 408 × p, then find the value of p. (2 marks)
Ans. HCF of 408 and 1032 is 24.
1032 × 2 + 408 × (p) = 24
408p = 24 – 2064
p = -5
Comments