Euclids Division Algorithm

We at ask-math believe that educational material should be free for everyone. Please use the content of this website for in-depth understanding of the concepts. Additionally, we have created and posted videos on our youtube.

We also offer One to One / Group Tutoring sessions / Homework help for Mathematics from Grade 4th to 12th for algebra, geometry, trigonometry, pre-calculus, and calculus for US, UK, Europe, South east Asia and UAE students.

Affiliations with Schools & Educational institutions are also welcome.

Please reach out to us on [email protected] / Whatsapp +919998367796 / Skype id: anitagovilkar.abhijit

We will be happy to post videos as per your requirements also. Do write to us.

In this section we will discuss Euclids Division Algorithm.
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.

Theorem : If a and b are positive integers such that a = bq + r, then every common divisor of a and b is a common divisor of b and r, and vice-versa.
Proof : Let c be a common divisor of a and b. Then,
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:

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.

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.
---------------------------------------------------------------------------
Examples :
1) Use Euclid’s algorithm to find the 420 and 130.

Solution :
Step:1 Since 420 > 130 we apply the division lemma to 420 and 130 to get ,
420 = 130 x 3 + 30
Step:2 Since 30 ≠ 0 , we apply the division lemma to 130 and 30 to get
130 = 30 x 4 + 10
Step:3 Since 10 ≠ 0 , we apply the division lemma to 30 and 10 to get
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.

Solution :
Step:1 Since 117 > 65 we apply the division lemma to 117 and 65 to get ,
117 = 65 x 1 + 52
Step:2 Since 52 ≠ 0 , we apply the division lemma to 65 and 52 to get
65 = 52 x 1 + 13
Step:3 Since 13 ≠ 0 , we apply the division lemma to 52 and 13 to get
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's Geometry

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

From Euclid Geometry to Real numbers

Home Page

Russia-Ukraine crisis update - 3rd Mar 2022

The UN General assembly voted at an emergency session to demand an immediate halt to Moscow's attack on Ukraine and withdrawal of Russian troops.