•  
agra,ahmedabad,ajmer,akola,aligarh,ambala,amravati,amritsar,aurangabad,ayodhya,bangalore,bareilly,bathinda,bhagalpur,bhilai,bhiwani,bhopal,bhubaneswar,bikaner,bilaspur,bokaro,chandigarh,chennai,coimbatore,cuttack,dehradun,delhi ncr,dhanbad,dibrugarh,durgapur,faridabad,ferozpur,gandhinagar,gaya,ghaziabad,goa,gorakhpur,greater noida,gurugram,guwahati,gwalior,haldwani,haridwar,hisar,hyderabad,indore,jabalpur,jaipur,jalandhar,jammu,jamshedpur,jhansi,jodhpur,jorhat,kaithal,kanpur,karimnagar,karnal,kashipur,khammam,kharagpur,kochi,kolhapur,kolkata,kota,kottayam,kozhikode,kurnool,kurukshetra,latur,lucknow,ludhiana,madurai,mangaluru,mathura,meerut,moradabad,mumbai,muzaffarpur,mysore,nagpur,nanded,narnaul,nashik,nellore,noida,palwal,panchkula,panipat,pathankot,patiala,patna,prayagraj,puducherry,pune,raipur,rajahmundry,ranchi,rewa,rewari,rohtak,rudrapur,saharanpur,salem,secunderabad,silchar,siliguri,sirsa,solapur,sri-ganganagar,srinagar,surat,thrissur,tinsukia,tiruchirapalli,tirupati,trivandrum,udaipur,udhampur,ujjain,vadodara,vapi,varanasi,vellore,vijayawada,visakhapatnam,warangal,yamuna-nagar
Euclids Division Lemma

EUCLID’S DIVISION LEMMA

We have already explored the world of real numbers and encountered irrational numbers. We will continue our discussion on real numbers and learn one of the important properties called Euclid’s division lemma.

LEMMA

A statement that is utilized to prove another statement can be defined as a Lemma.

ALGORITHM

A system of steps that are used to solve a problem is defined as an algorithm. Euclid’s division lemma and algorithm are closely interlinked with each other. The Euclid division lemma/algorithm has several applications related to finding properties of numbers.

EUCLID’S DIVISION LEMMA

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

PROOF:

Now, let us try finding the integers q and r for the following pair of positive integers a and b.

(1)  10, 3 (2)  20, 4 (3)  40, 19

Let us write the relation for each pair.

 1. Let a = 10 and b = 3

  Therefore, 10 = 3 × 3 + 1

  Here, q = 3 and r = 1, where 0 ≤ 1 < 3

 2. Let a = 20 and b = 4

  Therefore, 20 = 4 × 5 + 0

  Here, q = 5 and r = 0, where 0 ≤ 0 < 4

 3. Let a = 40 and b = 19

  Therefore, 40 = 19 × 2 + 2

  Here, q = 2 and r = 2, where 0 ≤ 2 < 19

If we observe from the above, 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

It can also be noticed that q and r are unique. Note that q and r can also be zero.

Hence, it is proved.

Finding HCF By Euclid’s Division Lemma

As we learned above, Euclid's division lemma has several applications related to the properties of numbers. We use Euclid's division lemma to find HCF. We can find the HCF of large numbers, which usually takes a lot of time with general calculations. Euclid's division lemma makes our workflow easier in finding the HCF of a number.

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

  1. Apply Euclid's division lemma to s and t such that there exist unique integers q and r satisfying s = tq + r, 0 ≤ r < t.
  2. If r = 0, then t is the HCF of s and t.
  3. If r ≠ 0, then apply division lemma to t and r.
  4. Continue this process until remainder = 0, and the divisor at this particular stage will be the HCF.

EXAMPLE: Use Euclid’s division lemma to find the HCF of 3814 and 2562.

SOLUTION: Here a = 3814 and b = 2562

Euclid’s division lemma, a = bq + r, 0 ≤ r < b, we get,

3814 = 2562 × 1 + 1252

Since r ≠ 0, continue the process by taking

a = 2562 and b = 1252.

2562 = 1252 × 2 + 58 ( r ≠ 0 )

1252 = 58 × 21 + 34 (r ≠ 0)

58 = 34 × 1 + 24 (r ≠ 0)

34 = 24 × 1+10 (r ≠ 0)

24 = 10 × 2 +4 (r ≠ 0)

10 = 4 × 2 + 2 (r ≠ 0)

4 = 2 × 2 + 0 (r = 0)

The remainder has now become zero, so stop the procedure. Since the divisor at this stage is 2, the HCF of 3814 and 2562 is 2.

Hence we can find the HCF of any number by using Euclid’s division lemma.

NEET Related Links

NEET Exam 

NEET  Exam Dates

NEET  Exam pattern

NEET  Syllabus

NEET  Eligibility Criteria

NEET  Application

NEET UG Counselling

NEET FAQ

NEET UG Result

NEET  Cut Off

JEE MAIN Related Links

JEE Main 

JEE Main Rank Predictor 

JEE Main College Predictor 

JEE Main  Exam Dates

JEE Main  Exam pattern

JEE Main  Application

JEE Main  Eligibility Criteria

JEE Main  Syllabus

JEE Main  Physics Syllabus

JEE Main  Maths Syllabus

JEE Main  Chemistry Syllabus

JEE Main  Admit Card

JEE Main  Counselling

JEE Main marks vs rank vs percentile

JEE Advanced Related Links

JEE Advanced  Exam Dates

JEE Advanced  Application

JEE Advanced  Eligibility Criteria

JEE Advanced  Syllabus

JEE Advanced  Maths Syllabus

JEE Advanced  Physics Syllabus

JEE Advanced  Chemistry Syllabus

JEE Advanced Exam Result

JEE Advanced Exam Dates

JEE Advanced Registration Dates

CUET Related Links

CUET  Eligibility Criteria

CUET  Admit Card

CUET  Exam Pattern

CUET  FAQs

CUET  Counselling

CUET  Syllabus

CUET  Result

CUET  Answer Key

CUET  Preparation

CUET CUTOFF

CUET  Application Form

Important Topics

Talk to our expert
Resend OTP Timer =
By submitting up, I agree to receive all the Whatsapp communication on my registered number and Aakash terms and conditions and privacy policy