Create New Account
Create New Account

Sign in to Innings2

or

New Account     Reset Password     

    Euclid’s Division Lemma

Powered by Innings 2

Reset Progress

This will delete your progress and chat data for all chapters in this course, and cannot be undone!

Glossary

Select one of the keywords on the left…

6th class > > Euclid’s Division Lemma

Euclid’s Division Lemma

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 take the facts given to us and write the corresponding equations to see if we can glean some insights. Converting a problem statement in english to mathematical language(variable) form is the first step to solving problems. Let's go through the facts one by one:

  1. My basket cannot accomodate more than 150 eggs. So if we assume 'a' to be the number of eggs, then a is less than or equal to 150.
  2. If counted in pairs, one will remain; So we know 'a' is a odd number and can be represented as a=.
  3. If counted in threes, two will remain; If we assume there are 't' groups of 3 we can represent a=.
  4. Similarly we get a=4s+3, a=5w+4, a=6q+5, a=7p+0 from the remaining facts.

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.

From the facts, clearly a is a mulitple of .

Also, from all the equations we see that when divided by 2,3,4,5,6 the remainder is always one less than the divisor(6q+5, 5w+4 etc).

So 'a' is one less than the LCM of 2,3,4,5,6.

The LCM of 2,3,4,5,6 is

So x can be 60-1=59.

But 59 does not satisfy one fact from the equations of the puzzle.

The next multiple of 60 is 120 and hence 'a' can be .

You will find that this value satisfies all the equations above.

Great. It's good we solved the puzzle. But how did that help us to learn about Euclid's lemma?

When we were writing the equations for the facts, we found that for any number we were able to represent it as a=b*q+r. It turns out that this is true for all positive integers.

Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

Turns out, we can use this lemma to find the HCF of two numbers. Lets see.

Find the HCF of 455 and 42.

Using Euclid's lemma we should be able to get 455 using 42. 455=42*+

Now consider 42 and 35. 42= 35*+

Repeating as above consider 35 and 7. 35= 7*+

We have got a remainder of 0. So we can stop. The divisor at this is stage is 7 and that is the HCF of 455 and 42.