We have seen that the said lemma is nothing but a restatement of the long division process which we have been using all these years. In this section, we will learn one more application of Euclids division lemma known as Euclids Division Algorithm.

An algorithm means a series of well defined steps which provide a procedure of calculation repeated successively on the results of earlier steps till the desired result is obtained.

c| a ⇒ a = cq1 for some integer q1

c| b ⇒ b = cq2 for some integer q2.

Now, a = bq + r

⇒ r = a – bq

⇒ r = cq1 – cq2 q

⇒ r = c( q1 – q2q)

⇒ c | r

⇒ c| r and c | b

⇒ c is a common divisor of b and r.

Hence, a common divisor of a and b is a common divisor of b and r.

Euclids Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

---------------------------------------------------------------------------

Let us state Euclid’s division algorithm clearly.

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.

---------------------------------------------------------------------------

1) Use Euclid’s algorithm to find the 420 and 130.

420 = 130 x 3 + 30

130 = 30 x 4 + 10

30 = 10 x 3 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 10, the HCF of 420 and 130 is 10.

---------------------------------------------------------------------------

2) Use Euclid’s algorithm to find the 65 and 117.

117 = 65 x 1 + 52

65 = 52 x 1 + 13

52 = 13 x 4 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 13, the HCF of 117 and 52 is 13.

• Euclid Geometry

• Euclids division lemma

• Euclids division Algorithm

• Fundamental Theorem of Arithmetic

• Finding HCF LCM of positive integers

• Proving Irrationality of Numbers

• Decimal expansion of Rational numbers

Home Page