For any given positive integers a and b, there exists unique integers q and r such that
a = bq + r where 0 ≤ r < b
Note: If b divides a, then r = 0
For a = 15, b = 3, it can be observed that
15 = 3 × 5 + 0
Here, q = 5 and r = 0
If b divides a, then 0 < r < b
For a = 20, b = 6, it can be observed that 20 = 6 × 3 + 2
Here, q = 6, r = 2, 0 < 2 < 6
Euclid’s division algorithm is a series of well-defined steps based on “Euclid’s division lemma”, to give a procedure for calculating problems.
Steps for finding HCF of two positive integers a and b (a > b) by using Euclid’s division algorithm:
Step 1: Applying Euclid’s division lemma to a and b to find whole numbers q and r, such that a = bq + r, 0 ≤ r < b
Step 2: If r = 0, then HCF (a, b) = b
If r ≠ 0, then again apply division lemma to b and r
Step 3: Continue the same procedure till the remainder is 0. The divisor at this stage will be the HCF of a and b.
To view the complete topic, please