. Euclid’s Division Algorithm In the previous section, we have studied about Euclid’s division lemma and its applications. We now study the concept Euclid’s Division Algorithm. The word ‘algorithm’ comes from the name of th century Persian Mathematician Al-khwarizmi.
An algorithm means a series of methodical step-by-step procedure of calculating successively on the results of earlier steps till the desired answer is obtained. Euclid’s division algorithm provides an easier way to compute the Highest Common Factor (HCF) of two given positive integers. Let us now prove the following theorem. Theorem If a and b are positive integers such that a bq + , then every common divisor of a and b is a common divisor of b and r and vice-versa.
Euclid’s Division Algorithm To find Highest Common Factor of two positive integers a and b , where a > b Step1: Using Euclid’s division lemma a bq ; ≤ < b . where q is the quotient, r is the remainder. If r = then b is the Highest Common Factor of a and b . Step : Otherwise applying Euclid’s division lemma divide b by r to get b rq , ≤ < Step : If r then r is the Highest common factor of a and b .
Step : Otherwise using Euclid’s division lemma, repeat the process until we get the remainder zero. In that case, the corresponding divisor is the HCF of a and b .