Euclid's Division Lemma & Euclid's Division Algorithm

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

This result was  first recorded in Book VII of Euclid’s Elements.

1. Find q and r for the following pairs of positive integers a and b, satisfying a = bq + r.
   (i) a = 13, b = 3 (ii) a = 80, b = 8 (iii) a = 125, b = 5 (iv) a = 132, b = 11

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.

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

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

5. Use Euclid’s division lemma to show that the square of any positive integer is either of the form 3m or 3m + 1 for some integer m.
   [Hint : Let x be any positive integer then it is of the form 3q, 3q + 1 or 3q + 2. Now square each of these and show that they can be rewritten in the form 3m or 3m + 1.]

6. Use Euclid’s division lemma to show that the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8. 

7. In a garden of flowers, a swarm of bees is setting in equal number on flowers. When they settle on two flowers, one bee will be left out. When they settle on three flowers, two bees will be left out. When they settle on four flowers, three bees will be left out. Similarly, when they settle on five flowers no bee will be left out. If there are at most fifty bees, how many bees are there in the swarm? 

8. 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 accommodate more than 150 eggs.
   So, how many eggs were there? 
   

  Using  division algorithm, if 25 is expressed as, 25= 4q+r, then the value of r is ....A]0 B]1 C]2 D]3 [ TS AD ]

Application  of EDL - Euclid's Division Algorithm

 It is process of finding HCF of two numbers which is based on  Euclid’s division lemma. The HCF of any two positive integers a and b, with a > b, is obtained as follows:
Step 1 : Apply the division lemma to find q and r where a = bq + r, 0 ≤ r < b.
Step 2 : If r = 0, the HCF is b. If r ≠ 0, apply Euclid’s lemma to b and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be HCF (a, b). Also, HCF(a, b) = HCF(b, r).

 1.Use Euclid’s division algorithm/Euclid's Division lemma to find the HCF of : 

1. 135 and 225 
2. 196 and 38220
3.  867 and 255
4.  81 and 237 
5.  900 and 270 
6.  1651 and 2032 
7. 4052 and 12576.
8. 220 and 40   [SCERT AP MP 2022 ]
9.  60 and 100  [ AP SSC 2018 M]
10.  1260 and 1440  [ AP SSC 2019 M] 

Other Questions

1.The remainder  obtained when any prime number greater than 6 is divided by 6 must be [Campus Recruitment 2007 ]

1. either 1 or 2  
2. either 1 or 3 
3. either 1 or 5 
4. either 3 or 5  

2.Consider the following sstatements for the sequence of numbers given below:

11,111,1111,11111,....

1.Each number can be expressed in the form of (4m=3), where m is a natual number

2.Some numbers are squares  

which of the  following statement(s) is/are correct?  [CDS 2016]

1.  1 only  
2. 2 only 
3. both 1 and 2  
4. neither 1 nor 2

For  NCERT Exemplar Problems on Real Numbers(Class-X) Click here