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