Euclid's division algorithm

Introduction to Euclid’s division algorithm 

Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. 

Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

The HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

Formula of Euclid’s division algorithm :

a = bq + r, 0 ≤ r < b

 Step By Step Solution of Euclid's division algorithm:

Suppose we need to find the HCF of the integers 455 and 42. 

We start with the larger integer, that is, 455. 

Then we use Euclid’s lemma to get

Now consider the divisor 42 and the remainder 35, and apply the division lemma to get

Now consider the divisor 35 and the remainder 7, and apply the division lemma to get

• Notice that the remainder has become zero, and we cannot proceed further. 

• We claim that the HCF of 455 and 42 is the divisor at this stage, i.e., 7.