]]>
LearnNext
##### Get a free home demo of LearnNext

Available for CBSE, ICSE and State Board syllabus.
Call our LearnNext Expert on 1800 419 1234 (tollfree)
OR submit details below for a call back

clear

# Euclid's Division Lemma

2,88,597 Views
Have a doubt? Clear it now.
live_help Have a doubt, Ask our Expert
format_list_bulleted Take this Lesson Test

#### Euclid's Division Lemma - Lesson Summary

You were introduced to the world of real numbers in class 9. In this chapter, we will continue our discussion of real numbers beginning with two important properties of positive integers. One is Euclid's division algorithm which will be dealt with here, another is Fundamental Theorem of Arithmetic which will be dealt with in the next lesson.

A dividend can be written as, Dividend = Divisor × Quotient + Remainder. This brings to Euclid's division lemma.

Euclidâ€™s division lemma:
Euclidâ€™s division lemma, states that for any two positive integers â€˜aâ€™ and â€˜bâ€™ we can find two whole numbers â€˜qâ€™ and â€˜râ€™ such that a = b × q + r  where 0 â‰¤ r < b.

Euclidâ€™s division lemma can be used to find the highest common factor of any two positive integers and to show the common properties of numbers.

The following steps to obtain H.C.F using Euclidâ€™s division lemma:
1. Consider two positive integers â€˜aâ€™ and â€˜bâ€™ such that a > b. Apply Euclidâ€™s division lemma to the given integers â€˜aâ€™ and â€˜bâ€™ to find two whole numbers â€˜qâ€™ and â€˜râ€™ such that, a = b x q + r.
2. Check the value of â€˜râ€™. If r = 0 then â€˜bâ€™ is the HCF of the given numbers. If r â‰  0, apply Euclidâ€™s division lemma to find the new divisor â€˜bâ€™ and remainder â€˜râ€™.
3. Continue this process till the remainder  becomes zero. In that case the value of the divisor â€˜bâ€™ is the HCF (a , b). Also HCF(a ,b) = HCF(b, r).

Euclidâ€™s division algorithm can also be used to find some common properties of numbers.