Euclid's Division Lemma: Proof, Finding HCF & Examples

Collegedunia Team logo

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

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.

Euclid’s Division Algorithm

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:

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

HCF (865, 255) using Euclid’s division lemma

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

HCF of 255 and 867 by Euclid’s division algorithm

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

CBSE X Related Questions

  • 1.
    Prove that \(\dfrac{\sin \theta}{1 + \cos \theta} + \dfrac{1 + \cos \theta}{\sin \theta} = 2\csc \theta\)


      • 2.
        AB and CD are diameters of a circle with centre O and radius 7 cm. If \(\angle BOD = 30^\circ\), then find the area and perimeter of the shaded region.


          • 3.

            In the adjoining figure, TS is a tangent to a circle with centre O. The value of $2x^\circ$ is

              • 22.5
              • 45
              • 67.5
              • 90

            • 4.

              Given that $\sin \theta + \cos \theta = x$, prove that $\sin^4 \theta + \cos^4 \theta = \dfrac{2 - (x^2 - 1)^2}{2}$.


                • 5.

                  Directions: In Question Numbers 19 and 20, a statement of Assertion (A) is followed by a statement of Reason (R).
                  Choose the correct option from the following:
                  (A) Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
                  (B) Both Assertion (A) and Reason (R) are true, but Reason (R) is not the correct explanation of Assertion (A).
                  (C) Assertion (A) is true, but Reason (R) is false.
                  (D) Assertion (A) is false, but Reason (R) is true.

                  Assertion (A): For any two prime numbers $p$ and $q$, their HCF is 1 and LCM is $p + q$.
                  Reason (R): For any two natural numbers, HCF × LCM = product of numbers.

                    • Both Assertion (A) and Reason (R) are true and Reason (R) is the correct explanation of Assertion (A).
                    • Both Assertion (A) and Reason (R) are true, but Reason (R) is not the correct explanation of Assertion (A).
                    • Assertion (A) is true, but Reason (R) is false.
                    • Assertion (A) is false, but Reason (R) is true.

                  • 6.
                    Find the zeroes of the polynomial \(2x^2 + 7x + 5\) and verify the relationship between its zeroes and coefficients.

                      Comments


                      No Comments To Show