Mathematics

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.