HCF Using Euclid's division lemma Calculator

Here, a and b are given numbers whereas q and r are Quotient and Reminder.

To find the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm. Highest Common Factor (HCF) of two or more numbers is the greatest common factor of the given set of numbers. If we consider two numbers to find the HCF using Euclid’s Division Lemma Algorithm then we need to choose the largest integer first to satisfy the statement, a = bq+r where 0 ≤ r ≤ b.

Let’s get deep to see how the algorithm works when finding the HCF of two or more given numbers.

An Introduction to Euclid's Division Lemma

Euclid’s Division Lemma states that if we have two positive integers a and b, then there are unique integers q and r which satisfies the requirement,

 a = bq + r

here, 0 ≤ r < b.

The Euclidean division algorithm is based on Euclid’s division lemma. It is also called the long division process.

Mathematically, this algorithm can be expressed as a dividend that will be equal to a divisor multiplied by the quotient added with the remainder i.e represented as Dividend = (Divisor × Quotient) + Remainder.

Euclid’s division lemma is used to compute the Highest Common Factor (HCF) of a pair of positive integers a and b. As H.C.F is the largest number which divides two or more positive integers exactly. This implies, that on dividing both the integers a and b the outcome is zero.

Steps To Find HCF Using Euclid's division lemma 

To evaluate the HCF of two positive integers, let's take them as c and d, with c > d, proceed with the following steps below:

• Firstly, Apply Euclid’s division lemma, to c and d. So, the whole numbers, q and r will be like 

 c = DQ + r, 0 ≤ r < d.

• If r = 0, d will be the HCF of c and d. If r ≠ 0, refer to the division lemma to d and r.
• Continue calculating with the above steps till you get the remainder as zero. The divisor at this stage or the last divisor will be assigned as HCF.

Special Case: If One of the Two Original Numbers is 0

As mentioned above if,

 r = 0

Then d will be the HCF of c and d.

OR

In other words,

If (x, 0) are two numbers,

Then HCF of x and 0 will be x

i.e HCF(x, 0) = x

Because zero has infinite factors.

Solved Example Using Euclidean Algorithm For Finding HCF of Two Numbers

Example: 

 Use Euclid's division algorithm to find the HCF of 276 and 726.

Solution: 

• Because 726 is smaller than 275,

 726 > 275

This, by applying Euclid's division lemma to 726 with 275 as the divisor,

726 = 275 × 2 + 176

• Because the remainder is not equal to 0, we apply the division lemma to 275 with 176 as the divisor

275 = 176 × 1 + 99

• Because the remainder is not equal to 0, we apply the division lemma to 176 with 99 as the divisor

176 = 99 × 1 + 77

• Still the remainder is 77 ≠ 0, we apply the division lemma to 99 with 77 as the divisor

99 = 77 × 1 + 22

• Still the remainder 22 ≠ 0, we apply the division lemma to 77 with 22 as the divisor

77 = 22 × 3 + 11

• Still the remainder 11 ≠ 0, we apply the division lemma to 22 with 11 as the divisor

22 = 11 × 2 + 0

Finally, the remainder is zero. So the process stops with this step.

The divisor at this phase is 11. So, the HCF(726, 275) = 11.

Visit our website hcflcm.com for such calculators to help you make your calculations easier and faster.

FAQs on HCF Using Euclid Division Lemma

• What is the HCF of 867 and 255 by Euclid division lemma?

By applying the Euclid division lemma we can determine the HCF of 867 and 255 as 51.

• How to use Euclid's division lemma?

We can use Euclid's division lemma to determine the HCF of two large numbers using the statement,

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

• What is Euclid's division lemma with example?

We can simply represent the lemma as Dividend = (Divisor × Quotient) + Remainder. For example 9=(4×2)+1

• What is Euclid division algorithm class 10?

This is a simple technique required to calculate the HCF for any two numbers (positive integers).