Long Term Courses *    67 Selections in IIT JEE 2012 *    192 Selections in AIEEE 2012 *    19 Selections in AIPMT 2012 *    330 Students score 90% + in CBSE-XII Board 2013 *    445 Students score 10 CGPA in CBSE-X Board 2013
Attend Free Demo Class Now
Name
 
Contact Number
 
 
Email ID
 
 
Class
 
City
 
   
 
Contact our Toll Free Nos
  • India Toll Free : 1-800-3070-0017
  • Bahrain (National) : 973-16198627
  • Indonesia Toll Free : 1-803-015-204-5864
  • Singapore (National) : 65-31586005
  • USA/Canada Toll Free : 1-888-442-3128
  • Others : +91-9899713975
 
operations_kei 09718199348 Login Reg
IITians @ your home
ISO 9001:2008 Certified

EUCLID’S DIVISION LEMMA
Euclid’s Division Lemma

Consider the following folk puzzle.

A trader was moving along a road selling eggs. An idler who didn’t have much work to do, started to get the trader into a wordy duel. This grew into a fight, he pulled the basket with eggs and dashed it on the floor. The eggs broke. The trader requested the Panchayat to ask the idler to pay for the broken eggs. The Panchayat asked the trader how many eggs were broken. He gave the following response:

If counted in pairs, one will remain;
If counted in threes, two will remain;
If counted in fours, three will remain;
If counted in fives, four will remain;
If counted in sixes, five will remain;
If counted in sevens, nothing will remain;
My basket cannot accomodate more than 150 eggs.

So, how many eggs were there? Let us try and solve the puzzle. Let the number of eggs be a. Then working backwards, we see that a is less than or equal to 150:

If counted in sevens, nothing will remain, which translates to a = 7p + 0, for some natural number p. If counted in sixes, a = 6q+5. If counted in fives, four will remain. It translates to a = 5r + 4, for some natural number q. If counted in fours, three will remain. It translates to a = 4s + 3, for some natural number s. If counted in threes, two will remain. It translates to a = 3t + 2, for some natural number t. If counted in pairs, one will remain. It translates to a = 2u + 1, for some natural number u.

That is, in each case, we have a and a positive integer b (in our example, b takes values 7, 6, 5, 4, 3 and 2, respectively) which divides a and leaves a remainder r (in our case, r is 0, 5, 4, 3, 2 and 1, respectively), that is smaller than b. The moment we write down such equations we are using Euclid’s division lemma, which is given in Theorem 1.

Getting back to our puzzle, do you have any idea how you will solve it? Yes! You must look for the multiples of 7 which satisfy all the conditions. By trial and error, you will find he had 119 eggs. In order to get a feel for what Euclid’s division lemma is, consider the following pairs of integers:

Fig-Real Numbers

We can write the following relations for each such pair:

17 = 6 × 2 + 5 (6 goes into 17 twice and leaves a remainder 5)
5 = 12 × 0 + 5 (This relation holds since 12 is larger than 5)
20 = 4 × 5 + 0 (Here 4 goes into 20 five-times and leaves no remainder)

That is, for each pair of positive integers a and b, we have found whole numbers q and r, satisfying the relation:

a = bq + r, 0 ≤ r < b

Note that q or r can also be zero.

Theorem 1 (Euclid’s Division Lemma) : Given positive integers a and b,there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

This result was perhaps known for a long time, but was first recorded in Book VII of Euclid’s Elements. Euclid’s division algorithm is based on this lemma.

An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.
The word algorithm comes from the name of the 9th century Persian mathematician al-Khwarizmi. In fact, even the word ‘algebra’ is derived from a book, he wrote, called Hisab al-jabr w’al-muqabala.
A lemma is a proven statement used for proving another statement.

Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

Suppose we need to find the HCF of the integers 455 and 42. We start with the larger integer, that is, 455. Then we use Euclid’s lemma to get

455 = 42 × 10 + 35

Now consider the divisor 42 and the remainder 35, and apply the division lemma to get

42 = 35 × 1 + 7

Now consider the divisor 35 and the remainder 7, and apply the division lemma to get

35 = 7 × 5 + 0

Notice that the remainder has become zero, and we cannot proceed any further.

We claim that the HCF of 455 and 42 is the divisor at this stage, i.e., 7. You can easily verify this by listing all the factors of 455 and 42. This method works because of the following result.

Euclid’s division algorithm

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:

Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.
Step 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.
This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.

Example 1 : Use Euclid’s algorithm to find the HCF of 4052 and 12576.

Solution :

Step 1 : Since 12576 > 4052, we apply the division lemma to 12576 and 4052, to get
12576 = 4052 × 3 + 420
Step 2 : Since the remainder 420 ≠ 0, we apply the division lemma to 4052 and 420, to get
4052 = 420 × 9 + 272
Step 3 : We consider the new divisor 420 and the new remainder 272, and apply the division lemma to get
420 = 272 × 1 + 148
We consider the new divisor 272 and the new remainder 148, and apply the division lemma to get
272 = 148 × 1 + 124
We consider the new divisor 148 and the new remainder 124, and apply the division lemma to get
148 = 124 × 1 + 24
We consider the new divisor 124 and the new remainder 24, and apply the division lemma to get
124 = 24 × 5 + 4
We consider the new divisor 24 and the new remainder 4, and apply the division lemma to get
24 = 4 × 6 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 4, the HCF of 12576 and 4052 is 4.

Notice that 4 = HCF (24, 4) = HCF (124, 24) = HCF (148, 124) = HCF (272, 148) = HCF (420, 272) = HCF (4052, 420) = HCF (12576, 4052).

Euclid’s division algorithm is not only useful for calculating the HCF of very large numbers, but also because it is one of the earliest examples of an algorithm that a computer had been programmed to carry out.

Remarks :

  1. Euclid’s division lemma and algorithm are so closely interlinked that people often call former as the division algorithm also.
  2. Although Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, i.e., b ≠ 0. However, we shall not discuss this aspect here.

Euclid’s division lemma/algorithm has several applications related to finding properties of numbers. Some examples of these applications given below:

Example 2 : Show that every positive even integer is of the form 2q, and that every positive odd integer is of the form 2q + 1, where q is some integer.

Solution : Let a be any positive integer and b = 2. Then, by Euclid’s algorithm, a = 2q + r, for some integer q ≥ 0, and r = 0 or r = 1, because 0 ≤ r < 2. So, a = 2q or 2q + 1.

If a is of the form 2q, then a is an even integer. Also, a positive integer can be either even or odd. Therefore, any positive odd integer is of the form 2q + 1.

Example 3 : Show that any positive odd integer is of the form 4q + 1 or 4q + 3, where q is some integer.

Solution : Let us start with taking a, where a is a positive odd integer. We apply the division algorithm with a and b = 4.
Since 0 ≤ r < 4, the possible remainders are 0, 1, 2 and 3.
That is, a can be 4q, or 4q + 1, or 4q + 2, or 4q + 3, where q is the quotient. However, since a is odd, a cannot be 4q or 4q + 2 (since they are both divisible by 2). Therefore, any odd integer is of the form 4q + 1 or 4q + 3.

Example 4 : A sweetseller has 420 kaju barfis and 130 badam barfis. She wants to stack them in such a way that each stack has the same number, and they take up the least area of the tray. What is the maximum number of barfis that can be placed in each stack for this purpose?

Solution :This can be done by trial and error. But to do it systematically, we find HCF (420, 130). Then this number will give the maximum number of barfis in each stack and the number of stacks will then be the least. The area of the tray that is used up will be the least.

Now, let us use Euclid’s algorithm to find their HCF. We have :
Fig-Real Numbers
So, the HCF of 420 and 130 is 10.
Therefore, the sweetseller can make stacks of 10 for both kinds of barfi.

Online Classroom Program Online Classroom Program 1 on 1 Online Classes 1 on 1 Online Classes Correspondence Course Correspondence Course Correspondence Course Best Pool of Faculty Result Oriented Coaching Program

Welcome to Kshitij Education India

Our Guarantee:

We're so sure you'll have the time of your life with us, we back our courses with a 100% Satisfaction Guarantee.

If for any reason you aren't 100% satisfied with your classes in first 7 days, just let us know and we'll refund your fees. No questions asked.

And based on your feedback, we will take the necessary steps to ensure we never repeat any mistakes as such.

Satisfaction Guaranteed
Live Chat