# Euclidean Algorithm Calculator

Enter two numbers below to find the greatest common factor between them using Euclid’s algorithm. If you want to find the greatest common factor for more than two numbers, check out our GCF calculator.

## Greatest Common Factor:

### Steps to Solve

**5**is the greatest common factor.

## How to Use Euclid’s Algorithm to Find the Greatest Common Factor

Euclid’s algorithm defines the technique for finding the greatest common factor of two numbers. The greatest common factor (GCF), also referred to as the greatest common divisor (GCD), is the largest whole number that divides evenly into all numbers in the set.

Euclid’s algorithm is a very efficient method for finding the GCF. To use Euclid’s algorithm, divide the smaller number by the larger number. If there is a remainder, then continue by dividing the smaller number by the remainder.

A ÷ B = Q_{1} remainder R_{1}

B ÷ R_{1} = Q_{2} remainder R_{2}

R_{1} ÷ R_{2} = Q_{3} remainder R_{3}

Continue this process until the remainder is 0 then stop. The divisor in the final step will be the greatest common factor.

**For example,** find the greatest common factor of 78 and 66 using Euclid’s algorithm.

78 ÷ 66 = 1 remainder 12

66 ÷ 12 = 5 remainder 6

12 ÷ 6 = 2 remainder 0

Thus, the greatest common factor is **6**, since that was the divisor in the equation that yielded a remainder of 0.

### What if One of the Two Original Numbers is 0?

If *either* number are 0 then by definition, the larger number is the greatest common factor. In this case it is unnecessary to use Euclid’s algorithm to find the GCF.

If *both* numbers are 0 then the GCF is undefined.

You’ll probably also be interested in our greatest common factor calculator which can find the GCF of more than two numbers.