Euclid’s Division Algorithm

This concept is based on Euclid’s division lemma. This is the technique to calculate the HCF (Highest common factor) of given two positive integers m and n,

To calculate the HCF of two positive integers’ m and n with m > n, the following steps are followed:

Step 1: Apply Euclid’s division lemma to find q and r where m = nq + r, 0 ≤ r < n.

Step 2: If the remainder i.e. r = 0, then the HCF will be ‘n’ but if r 0 then we have to apply Euclid’s division lemma to n and r.

Step 3: Continue with this process until we get the remainder as zero. Now the divisor at this stage will be HCF (m, n). Also, HCF (m, n) = HCF (n, r), where HCF (m, n) means HCF of m and n.