You are using an out dated version of Internet Explorer.  Some features may not work correctly. Upgrade to   Google Chrome     Dismiss

Select Board & Class

Login

Real Numbers

• Euclid’s Division Lemma

For any given positive integers a and b, there exists unique integers q and r such that

a = bq + r where 0 ≤ r < b

 

Note: If b divides a, then r = 0

 

Example 1: 

For a = 15, b = 3, it can be observed that

15 = 3 × 5 + 0

Here, q = 5 and r = 0

If b divides a, then 0 < r < b

 

Example 2: 

For a = 20, b = 6, it can be observed that 20 = 6 × 3 + 2

Here, q = 6, r = 2, 0 < 2 < 6

 

• Euclid’s division algorithm

Euclid’s division algorithm is a series of well-defined steps based on “Euclid’s division lemma”, to give a procedure for calculating problems.

 

Steps for finding HCF of two positive integers a and b (a > b) by using Euclid’s division algorithm:

 

Step 1: Applying Euclid’s division lemma to a and b to find whole numbers q and r, such that a = bq + r, 0 ≤ r < b

Step 2: If r = 0, then HCF (a, b) = b

If r ≠ 0, then again apply division lemma to b and r

Step 3: Continue the same procedure till the remainder is 0. The divisor at this stage will be the HCF of a and b.

 …

To view the complete topic, please

What are you looking for?

Syllabus