GCF Calculator · Practical guide
How to Find GCF Using the Euclidean Algorithm
Divide the larger number by the smaller, keep the remainder, and repeat until the remainder is zero.
At a glance
The Algorithm in One Sentence
To find the GCF of two numbers, repeatedly replace the larger number with the remainder of dividing the two: gcd(a, b) = gcd(b, a mod b). When the remainder reaches zero, the last non-zero divisor is the GCF. The calculator above prints these exact steps for any numbers you enter.
Interactive tool
GCF Calculator
Enter your own values, then compare the result with the examples below.
Results
Worked Example: gcd(48, 18)
- gcd(48, 18): 48 mod 18 = 12
- gcd(18, 12): 18 mod 12 = 6
- gcd(12, 6): 12 mod 6 = 0
- Result = 6
Check it: 48 ÷ 6 = 8 and 18 ÷ 6 = 3, and 8 and 3 share no factors, so 6 is indeed the greatest common factor.
Why It Works
Any number that divides both a and b also divides their difference, and therefore divides the remainder a mod b. So the common divisors of the pair (a, b) are exactly the common divisors of (b, a mod b). Each step shrinks the numbers while preserving the full set of common divisors, until zero forces the answer.
Why It Beats Listing Factors
Listing factors is fine for small numbers, but it scales badly. Finding gcd(1071, 462) by factoring means hunting primes; the Euclidean algorithm solves it in five quick divisions: 1071 mod 462 = 147, 462 mod 147 = 21, 147 mod 21 = 0, giving 21. For large integers it is dramatically faster, which is why computers use it.
Frequently Asked Questions
Who invented the Euclidean algorithm?
It is attributed to the Greek mathematician Euclid, who described it around 300 BC in his Elements. It is one of the oldest algorithms still in everyday use.
Does the order of the two numbers matter?
No. If you start with the smaller number first, the algorithm simply performs one extra swap step and converges to the same GCF.
What is the GCF if one number is a multiple of the other?
It is the smaller number itself. For example, gcd(12, 60) is 12, because 60 mod 12 equals 0 on the very first step.
Can the Euclidean algorithm handle three numbers?
Yes. Compute the GCF of the first two, then take the GCF of that result with the third number, and so on for longer lists.