Euclid’s Division Lemma
Given positive integers a and b, there exist
unique integers q and r which satisfies the condition a = bq + r where 0 ≤ r < b
To calculate the Highest Common Factor
(HCF) of two positive integers a and b we
use Euclid’s division algorithm. HCF is the largest number which exactly
divides two or more positive integers. That means, on dividing both the
integers a and b the remainder is zero.
Example:
Find the HCF of 81 and 675 using the Euclidean division algorithm.
Solution: The larger
integer is 675, therefore, by applying the Division Lemma a = bq + r where 0 ≤ r < b, we have
a =
675 and b =
81
⇒ 675 = 81 × 8 + 27
By applying Euclid’s
Division Algorithm again we have,
81 = 27 × 3 + 0
We cannot proceed further as
the remainder becomes zero. According to the algorithm, in this case, the
divisor is 27. Hence, the HCF of 675 and 81 is 27.
