For any two positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where 0 ≤ r < b.

**For Example**

(i) Consider number 23 and 5, then: 23 = 5 × 4 + 3

Comparing with a = bq + r; we get:

a = 23, b = 5, q = 4, r = 3 and 0 ≤ r < b (as 0 ≤ 3 < 5).

(ii) Consider positive integers 18 and 4.

18 = 4 × 4 + 2

↠ For 18 (= a) and 4(= b) we have q = 4,

r = 2 and 0 ≤ r < b.

In the relation a = bq + r, where 0 ≤ r < b is nothing but a statement of the long division of number a by number b in which q is the quotient obtained and r is the remainder.

Thus, dividend = divisor × quotient + remainder ↠ a = bq + r

**H.C.F. (Highest Common Factor) ** The H.C.F. of two or more positive integers is the largest positive integer that divides each given positive number completely.

i.e., if positive integer d divides two positive integers a and b then the H.C.F. of a and b is d.

For Example

(i) 14 is the largest positive integer that divides 28 and 70 completely; therefore H.C.F. of 28 and 70 is 14.

(ii) H.C.F. of 75, 125 and 200 is 25 as 25 divides each of 75, 125 and 200 completely and so on.

**Using Euclid's Division Lemma For Finding H.C.F. **

Consider positive integers 418 and 33.

**Step-1 : ** Taking bigger number (418) as a and smaller number (33) as b express the numbers as a = bq + r

↠ 418 = 33 × 12 + 22

**Step-2 : ** Now taking the divisor 33 and remainder 22; apply the Euclid's division algorithm to get:

33 = 22 × 1 + 11 [Expressing as a = bq + r]

**Step-3** Again with new divisor 22 and new remainder 11; apply the Euclid's division algorithm to get:

22 = 11 × 2 + 0

**Step-4**

Since, the remainder = 0 so we cannot proceed further.

**Step-5**

The last divisor is 11 and we say H.C.F. of 418 and 33 = 11

**Verification :**** (i) Using factor method:**

∴ Factors of 418 = 1, 2, 11, 19, 22, 38, 209 and 418 and,

Factor of 33 = 1, 3, 11 and 33.

Common factors = 1 and 11

↠ Highest common factor = 11 i.e., H.C.F. = 11

**(ii) Using prime factor method:**

Prime factors of 418 = 2, 11 and 19.

Prime factors of 33 = 3 and 11.

∴ H.C.F. = Product of all common prime factors = 11. For any two positive integers a and b which can be expressed as a = bq + r, where 0 ≤ r < b, the, H.C.F. of (a, b) = H.C.F. of (q, r) and so on. For number 418 and 33

418 = 33 × 12 + 22

33 = 22 × 1 + 11

and 22 = 11 × 2 + 0

↠ H.C.F. of (418, 33) = H.C.F. of (33, 22) = H.C.F. of (22, 11) = 11.

SHOW CHAPTERS