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

GMAT

GRE

1st Grade

2nd Grade

3rd Grade

4th Grade

5th Grade

6th Grade

7th grade math

8th grade math

9th grade math

10th grade math

11th grade math

12th grade math

Precalculus

Worksheets

Chapter wise Test

MCQ's

Math Dictionary

Graph Dictionary

Multiplicative tables

Math Teasers

NTSE

Chinese Numbers

CBSE Sample Papers