Euclid Division Lemma

Finding the best resources to fuel the spirit of succeeding in exams is one of the biggest challenges students face. Everybody knows that smart work has acquired as a more dominant position than hard work these days. And picking the right kind of resources is smart work but in the face of over availability of the content in the physical and the virtual market, being able to filter the right content has become a challenge in itself.  

To help the students equip themselves with the right and reliable resources, Vedantu has come up with the Euclid Division Lemma article that is available on its website. The article is prepared by the best of the teachers in India of the masters of their stream and is very committed to the student’s success in life.

The best part of Vedantu’s article is that it's free of cost and a student is not required to pay a single penny. Now studying the best of the best educational material is not just easy but also highly affordable. The beauty of this feature lies in this fact; it is accessible from any kind of device and any location. Even if you are sitting on the hilltops or the seashores with a decent internet connection, students can download the Euclid Division Lemma article in format for free. 

Euclid Division Algorithm

Euclid was the first Greek mathematician who initiated a new way to study Geometry. He is well known for his elements of Geometry. He also made important contributions to number theory, and one of them is Euclid’s Lemma.

A Lemma is a proven statement that is used to prove other statements.

Euclid’s division algorithm is based on Euclid’s Lemma. For many years we were using a long division process, but this lemma is a restatement of it.

State Euclid’s Division Lemma

Consider a and b be any two positive integers, unique integers q and r such that

If b|a, then r = 0. Otherwise, r satisfies the stronger inequality 0 < r < b

Euclid Division Lemma Definition

Theorem: Let a and b be any two positive integers then, there exist unique integers q and r such that

a = bq + r, 0<= r < b

If b|a, then r = 0. Otherwise, r satisfies the stronger inequality 0 <= r < b

Proof:

Step 1: 

Let us consider an Arithmetic Progression

………, a-3b, a - 2b, a - b, a, a + b, a + 2b, a + 3b…….

Here the common difference is b and it extends in both directions.

Step 2:

Let r is the smallest non-negative term of the arithmetic progression. Then there exists a non- negative integer q such that 

a - bq = r

a  = bq + r

Step 3: 

As, 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

Euclid’s Division Algorithm:

If ‘a’ and ‘b’ are positive integers such that a = bq + r, then every common divisor of ‘a’ and ‘b’, is a common divisor of ‘b’ and ‘r’ and vice versa.

Using Euclid’s Division Algorithm for Finding HCF

Consider positive integers 418  and 33

Step 1: 

Taking a bigger number 418 as a and smaller number 33 as b

Express the numbers in the form a = bq + r

418 = 33 x 12 +22

Step 2:

Now taking the divisor 33 as a and 22 as b apply Euclid’s Division algorithm to get,

33 = 22 x 1 + 11

Step 3:

Again take 22 as new divisor a and 11 as b apply Euclid’s Division Algorithm to get

22 = 11 x 2 + 0

Step 4:

Since, the remainder = 0 so we cannot proceed further.

Step 5:

The last divisor is 11 and we say H.C.F. of 418 and 33 is 11.

Euclid’s Lemma:

The Euclid Lemma is a theory proposed by Euclid. Euclid lemma is a proven statement used to prove other statements.

Solved Examples:

Example 1: To find HCF of 210 and 55 using Euclid’s division algorithm.

Solution: Given integers are 210 and 55. 

210>55

Applying Euclid’s division lemma to 210 and 55 we get,

210 = 55 x 3 + 45………………..(i) 

Since the remainder 45 is not equal to zero we apply the division lemma to the divisor 55 and remainder 45 to get,

55 =45 x 1 + 10………………….(ii)

Now, we apply division lemma to the new divisor 45 and new remainder 10 to get

45 = 10 x 4 + 5…………………….(iii)

We now consider the new divisor 10 and the new remainder 5 and apply division lemma to get

10 = 5 x 2 + 0

The remainder at this stage is 0. So the divisor at this stage or the remainder at the previous step is 5

So HCF of 210 and 55 is 5

Example 2: Using Euclid’s Division  Algorithm, find the H.C.F of  135 and 225

Solution: Given integers are 135 and 225

225>135

Applying Euclid’s division lemma, we get

225 = 135 x 1 + 90

Now taking divisor 135 and remainder 90, we get 

135 = 90 x1 + 45

Further taking divisor 90 and remainder 45, we get 

90 = 45 x 2 + 0

Now at this stage remainder is 0 so we get 45 as the H.C.F

Quiz Time:

1.Using Euclid’s division algorithm, find the H.C.F of 196 and 38220.

2.Using Euclid division algorithm find the H.C.F of 441 and 567 

Revision in Time 

It takes some smart efforts to store information in mind for a longer duration of time.  To consolidate all the information, one needs the help of revision notes. The above article is very precise in nature and would enable the students to make some really good revision notes just by a mere underling of the key concepts in the article.  The teachers of Vedantu have taken care that the article proves to be beneficial for the students from a 360-degree angle. It gives everything that the students need to know and on the other hand, it enables them to take notes in the fastest manner possible. 

Once the student has made the revision notes, she should go through it multiple times. Adopting this practice would ensure that students do not forget the important details when they go for the exams.

Free and Fair Content

On Vedantu, students can find ample content for free. Vedantu is committed to  quality education at a highly affordable price to all the students in India. This intent of the teachers at Vedantu seems to be turning true with more and more students adopting to study from the resources provided by the platform.

Be a part of the huge Vedantu student community by visiting the website and start learning today!