Facts that Matter
An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.
A lemma is a proven statement used for proving another statement.
- Euclid’s Division Lemma
For any two given positive integers ‘a’ and ‘b’ there exists unique whole numbers ‘q’ and ‘r’ such that
a = bq + r, where 0 ≥ r < b
Here, a = Dividend, b = Divisor
q = Quotient, r = Remainder
i.e., Dividend = (Divisor × Quotient) + Remainder
- Euclid’s Division Algorithm
Euclid’s Division Algorithm is a technique to compute the HCF of two positive integers ‘a’ and ‘b’ (a > b) using the following steps:
Step-I: Applying Euclid’s Lemma to a and b to find whole numbers ‘q’ and ‘r’ such that:
a = bq + r, 0 ≥ r < b
Step-II: If r = 0 then ‘b’ is the HCF of ‘a’ and ‘b’. If r ≠ 0 then apply the Euclid’s division lemma to ‘b’ and ‘r’.
Step-III: Continue the process till the remainder is zero, i.e., repeat the step-II again and again until r = 0. Then, the divisor at this stage will be the required H.C.F.
I. We state Euclid’s Divison Algorithm for positive integers only but it can be extended for all integers except zero i.e., b ≠ 0.
II. When ‘a’ and ‘b’ are two positive integers such that a = bq + r, 0 ≤ r < b then HCF (a, b) = HCF (b, r).
Fundamental Theorem of Arithmetic
Every composite number can be expressed as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur.