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
Joe is the creator of Inch Calculator and has over 20 years of experience in engineering and construction. He holds several degrees and certifications.
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 = Q1 remainder R1
B ÷ R1 = Q2 remainder R2
R1 ÷ R2 = Q3 remainder R3
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.