Euclid’s Division Algorithm | Definition and Application

Euclid’s Division Algorithm is a method devised by ancient Greek mathematician Euclid mainly to find the greatest common divisor (GCD) of two numbers. It has other applications too. Euclid’s Division Algorithm is called so because it is found by Euclid and is an example of an algorithm.

To understand Euclid’s Division Algorithm better we should first learn about Lemma and Algorithm in brief.

What is Lemma

A lemma is a proven statement used for proving another statement.

Euclid’s division Lemma

Given positive integers a and b, there exist unique integers q and r satisfying

a = bq + r, 0 ≤ r < b.

➢ This is a restatement of the long division process, and that the integers q and r are called the quotient and remainder respectively.

➢ It was first recorded in Book VII of Euclid’s Elements (c. 300 BC).

➢ Euclid’s division algorithm is based on this lemma.

What is Algorithm

An algorithm is a series of well defined steps which gives a procedure for solving a type of problem.

The word algorithm comes from the name of the 9th century Persian mathematician
Muhammad ibn Musa al-Khwarizmi (C.E. 780 – 850) . Even the word ‘algebra’ is derived from a book, he wrote, called Hisab al-jabr w’al-muqabala .

Euclid’s Division Algorithm

“Any positive integer a can be divided by another positive integer b in such a way that it leaves a remainder r that is smaller than b.”

➧ Series of steps based on Euclid’s division lemma is used to obtain the required result.

➧ Euclid’s division algorithm has several applications related to finding properties of numbers.

➧ It is mainly applied to compute the Highest Common Factor (HCF) of two given positive integers.

➧ It is one of the earliest examples of an algorithm that a computer had been programmed to carry out.

➧ Although Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, i.e.,b ≠ 0.

Application of Euclid’s Division Algorithm

HCF of two Positive Integers

To obtain the HCF of two positive integers, say u and v, with u > v, we follow the steps below:

Step 1 : Apply Euclid’s division lemma, to u and v. So, we find whole numbers, q and r such that

u = vq + r, 0 ≤ r < v.

Step 2 : If r = 0, v is the HCF of u and v. If r ≠ 0, apply the division lemma to v and r.

Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

Q) Use Euclid’s division algorithm to find the HCF of : 135 and 225.

(A) Step 1 : Since 225 > 135, we apply the division lemma to 225 and 135, to get

225 = 135 × 1 + 90

Step 2 : Since the remainder 90 ≠ 0, we apply the division lemma to 135 and 90, to get

135 = 90 ×1 + 45

Step 3 : We consider the new divisor 90 and the new remainder 45, and apply the division lemma to get

90 = 45 × 2 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 45, the HCF of 225 and 135 is 45.

Thus, we have learned about Euclid’s Division Algorithm and how to apply it to find HCF of two Numbers. We can similarly apply Euclid’s Division Algorithm to find the simplest form of a fraction.