# HCF Using Euclid’s Division Lemma | What is Euclid’s Division Lemma?

HCF Using Euclid’s Division Lemma Method: Finding the Highest Common Factor by Euclid’s Division Lemma Algorithm is a standard approach by all the students. Here, we will see the detailed process on How to Find HCF of two or more numbers by Euclid’s Division Lemma Algorithm.

## What is Euclid’s Division Lemma?

The basis of the Euclidean division algorithm is Euclid’s division lemma. Euclid’s division algorithm is a method to calculate the Highest Common Factor (HCF) of two or three given positive numbers. Euclid’s Division Lemma says that for any two positive integers suppose a and b there exist two novel whole numbers say q and r, such that, a = bq+r, where 0≤r<b.

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.

### How to Find the Highest Common Factor of given numbers Using Euclid’s Division Lemma?

Follow the below steps to find the HCF of given numbers with Euclid’s Division Lemma:

Step 1: Apply Euclid’s division lemma, to a and b. So, we find whole numbers, q and r such that a = bq + r, 0 ≤ r < b.
Step 2: If r = 0, b is the HCF of a and b. If r ≠ 0, apply the division lemma to d and r.
Step 3: Continue the process until the remainder is zero. The divisor at this stage will be the required HCF of a and b.

Thus, Euclid’s Division Lemma algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d,

Example: Use Euclid’s algorithm to find the HCF of 36 and 96.

Solution:

Given HCF of two numbers ie., 36 and 96.  The larger number from both a and b is 96, hence, apply the Euclid Division Lemma algorithm equation a = bq + r where 0 ≤ r ≤ b.

We have a= 96 and b= 36

⇒ 96 = 36 × 2 + 24, where 24≠0.

So, again apply the Euclid’s Division Algorithm for new dividend as 36 and divisor as 24

⇒ 36 = 24×1 +12, where 12≠0

Again take dividend as 24 and divisor as 12.

⇒ 24 = 12×2 +0, here reminder=0

As the remainder becomes zero, we can halt the process here itself. As per the Euclid’s division Lemma algorithm, the last divisor is 12.

Thus, the HCF of 36 and 96 is 12.

### FAQs on HCF of two or more numbers by Euclid’s Division Lemma

1. What is meant by Euclid’s Division Lemma?

The definition of Euclid’s Division Lemma is if two positive integers say “a” and “b”, then there exists unique integers state “q” and “r” such that which satisfies the condition a = bq + r where 0 ≤ r ≤ b.

2. What is Lemma?

Lemma is a proven statement used for proving another statement.

3. What represents Q and R in Euclid’s Division Lemma Technique?

The number ‘q’ is called the quotient and ‘r’ is called the remainder.

4. What is HCF of two or more numbers?

The full form of HCF is Highest Common Factor. The HCF of two or more given integers is defined as the greatest number which evenly divides a given set of numbers.

5. How to Find HCF using Euclid’s Division Lemma?

You can easily find HCF of a set of integers by Euclid’s division lemma along with a detailed explanation from our page. Enter the inputs and get the HCF of two or more numbers which is solved by using Euclid’s division lemma method with neat & understandable steps.