# Euclid’s Algorithm Calculator | Find the HCF using Euclid’s Division Lemma

There are several methods to find the GCF of a number while some being simple and the rest being complex. Of all the methods Euclid’s Algorithm is a prominent one and is a bit complex but is worth knowing. Enter the numbers you want to find the GCF or HCF and click on the Calculate Button to get the result in a short span of time.

Continue reading further to clarify your queries on what is Euclid’s Algorithm and how to use Euclid’s Algorithm to find the Greatest Common Factor. Unlike many other calculators out there this provides detailed steps explaining every minute detail.

HCF Using Euclid’s deivision lemma Calculator

Here are some samples of HCF Using Euclids Division Algorithm calculations.

## How to find GCF using Euclid’s Algorithm?

Follow the simple and easy procedures on how to find the Greatest Common Factor using Euclid’s Algorithm. Go through the steps and find the GCF of positive integers a, b where a>b.

Step 1: On applying Euclid’s division lemma to integers a and b we get two whole numbers q and r such that, a = bq+r ; 0 r < b.

Step 2: If r =0, then b is the HCF of a, b. If r is not equal to zero then apply Euclid’s Division Lemma to b and r.

Step 3: Continue the Process until the remainder is zero.

Step 4: When the remainder is zero, the divisor at this stage is called the HCF or GCF of given numbers.

Example

Find the GCF of 78 and 66 using Euclid’s Algorithm?

Solution:

Given numbers are 78 and 66

In the given numbers 66 is small so divide 78 with it.

Step 1: On dividing 78 ÷ 66 you will have the quotient 1 and remainder 12

Step 2: As the remainder isn’t zero continue the process and take the newly obtained remainder as a small number now.

Thus, 66 ÷ 12 you will have quotient 5 and remainder 6

Step 3: Since the remainder isn’t zero continue the process and you will get the result as follows

12÷6  where the quotient is 2 and the remainder is zero.

6 is the GCF of numbers as it is the divisor that yielded a remainder of zero.

### FAQs on Euclid’s Algorithm Calculator

1. What do you mean by Euclid’s Algorithm?

It is a method of finding the Greatest Common Divisor of numbers by dividing the larger by smaller till the remainder is zero.

2. Who invented the Euclid Algorithm?

Greek mathematician Euclid invented the procedure of repeated application of division to find the GCF or GCD.

3. How to use Euclid’s Algorithm Calculator?

You can use Euclid’s Algorithm tool to find the GCF by simply providing the inputs in the respective field and tap on the calculate button to get the result in no time.

4. What is Q and R in the Euclid’s Division?

Q and R mean Quotient and Remainder in the division.