- 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 algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.
- To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:
Step 1: Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.
Step 2: If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
Step 3: Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.