## REAL NUMBERS

EUCLID'S DIVISION LEMMA

Given positive integers a and b. there exist unique integers q and r satisfying a = bq + r where
0<  r <b,
Here we call 'a' as a dividend, 'b' as divisor 'q' as quotient and 'r' as the remainder,

Dividend = (Divisor x Quotient) + Remainder

If in Euclid's lemma r= 0 then b would be HCF of 'a' and 'b'.

### IMPORTANT QUESTIONS

Show that any positive even integer is of the form 6q, or 6q+ 2, or 6q + 4. where q is some integer.

Solution: Let x be any positive integer such that x >6, Then, by Euclid's algorithm, x = 6q +r for some integer q > 0 and 0 <  r < 6.
Therefore, x= 6q or 6q+1 or 6q + 2 or 6q + 3 or 6q + 4 or 6q + 5 .
Now, 6q is an even integer being a multiple of 2.
We know that the sum of  two even integers are always even integers.
Therefore, 6q+2 and 6q + 4 are even integers .
Hence any positive even integer is of the form 6q. or 6q + 2, or 6q + 4. where q is some integer,

#### Questions for practice

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

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

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

4. 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.

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

EUCLID'S DIVISION ALGORITHM

Euclid's division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

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

Step 1: Apply Euclid's division lemma, to c and d. So, we find whole numbers, q and r such that c =dq+r. 0 < r < d

Step 2: If r=0. d is HCF of c and d. If r is not equal 0 apply the division lemma to d and r .

Step 3: Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because of HCF (c,d) = HCF (d,r) where the symbol HCF (c,d) denotes the HCF of c and d, etc.

IMPORTANT QUESTIONS

Use Euclid's division algorithm to find the HCF of 867 and 255

Solution: Since 867 > 255, we apply the division lemma to 867 and 255 to obtain 867 = 255  X  3 + 102.
Since remainder    $102&space;\neq&space;0$ , we apply the division lemma to 255 and 102 to obtain.
255 = 102 X 2 + 51
We consider the new divisor 102 and new remainder 51, and apply the division lemma to obtain 102 = 51 X 2 + 0
Since the remainder is zero, the process stops.
Since the divisor at this stage is 51
Therefore, HCF of 867 and 255 is 51.

Questions for practice

1. Use Euclid's algorithm to find the HCF of 4052 and 12576.

2.Use Euclid's division algorithm to find the HCF of 135 and 225.

3. Use Euclid's division algorithm to find the HCF of 196 and 38220.

4. Use Euclid's division algorithm to find the HCF of 455 and 42.

5. Using Euclid's algorithm, find the HCF of (i) 405 and 2520 (ii) 504 and 1188  (iii) 960 and 1575