Greatest Common Factor Calculator
Find the greatest common factor (GCF) — also called the greatest common divisor (GCD) — of two integers using the Euclidean algorithm. The largest number that divides both inputs evenly; used everywhere from simplifying fractions to designing tilings to cryptography.
Last updated: May 2026
Compare with similar
About this calculator
The greatest common factor of two integers a and b is the largest positive integer that divides both without remainder. This calculator uses the Euclidean algorithm: starting with the absolute values of a and b, it repeatedly replaces (a, b) with (b, a mod b) until b becomes 0; the remaining a is the GCF. The runtime is O(log min(a, b)) — each step at least halves the larger value — so even astronomically large inputs (millions or billions of digits in cryptographic contexts) resolve almost instantly. Variables: num1 and num2 are the two integers; negatives are handled by taking absolute values, since the divisors of a negative number are the same as those of its absolute value. Edge cases worth knowing: gcd(0, 0) is conventionally defined as 0 (no greatest divisor exists, every integer divides 0); gcd(a, 0) = |a| for any a; if either input is 1, the gcd is 1 (1 divides everything). The gcd is always at least 1 and at most min(|a|, |b|). When gcd(a, b) = 1 the two integers are called coprime or relatively prime — a critical concept in number theory used in RSA encryption, modular arithmetic, and the Chinese Remainder Theorem. The gcd also obeys the identity lcm(a, b) · gcd(a, b) = a · b, so any GCF calculator implicitly answers LCM questions and vice versa. For three or more inputs the gcd is associative: gcd(a, b, c) = gcd(gcd(a, b), c).
How to use
Example 1 — Simplifying a fraction. To reduce 48/180 to lowest terms, find gcd(48, 180). Enter 48 and 180. Euclidean trace: gcd(180, 48) → 180 mod 48 = 36 → gcd(48, 36) → 48 mod 36 = 12 → gcd(36, 12) → 36 mod 12 = 0 → gcd = 12. ✓ Dividing both numerator and denominator by 12 gives 48/180 = 4/15, which is fully reduced because gcd(4, 15) = 1. Example 2 — Tiling problem. You want to tile a 24 m × 36 m floor with the largest possible square tiles, no cutting allowed. The tile side must divide both 24 and 36 evenly — i.e., it must be a common factor. The largest one is gcd(24, 36) = 12. ✓ So the optimal tile is 12 m × 12 m, requiring 2 × 3 = 6 tiles total. The same trick solves any "largest equal-piece divisibility" problem from cutting fabric to packaging cans.
Frequently asked questions
How is GCF (or GCD) different from LCM?
GCF/GCD is the largest number that divides both inputs evenly; LCM is the smallest number that both inputs divide into evenly. They are bound together by the identity GCD(a, b) · LCM(a, b) = a · b, so given one you immediately have the other for free. As a rule of thumb, GCF is always at most min(a, b), and LCM is always at least max(a, b). When the inputs are coprime (share no common factors other than 1), GCF = 1 and LCM = a · b — they pull in opposite directions. The two come up in different contexts: GCF for simplifying fractions, dividing into equal groups, or finding common divisors; LCM for synchronising periodic events or finding common denominators.
Why is the Euclidean algorithm so fast?
Each step of the Euclidean algorithm reduces the second number to (first mod second), which is strictly smaller than the second. In fact, the worst case (when the inputs are consecutive Fibonacci numbers) takes about log_φ(N) steps where φ = (1 + √5)/2 ≈ 1.618, the golden ratio — that is O(log N) where N is the larger input. For inputs with millions of digits, this still resolves in a few hundred steps. The algorithm is older than recorded mathematics in most cultures (Euclid wrote it down around 300 BC) and is still one of the most efficient algorithms in number theory. Modern variants like the binary GCD algorithm (which replaces division with shifts and subtraction) are even faster on computers because they avoid expensive division operations.
How do I find the GCF of three or more numbers?
Apply GCF pairwise: gcd(a, b, c) = gcd(gcd(a, b), c), and so on for any number of inputs. The result does not depend on the grouping order (GCF is associative and commutative), so gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) — you can chain in whatever order is most convenient. For example, gcd(24, 36, 60) = gcd(gcd(24, 36), 60) = gcd(12, 60) = 12. An alternative is to factor each input into primes and take the minimum exponent of each prime across the set; this is what most textbooks teach because it visualises the structure, but the pairwise Euclidean approach is much faster in practice.
What are the most common mistakes people make computing GCF?
The first is reporting one of the original numbers as the GCF without checking that it divides the other — for example, claiming gcd(24, 36) is 24 because 24 looks "smaller-ish" (it isn't; 24 does not divide 36). The second is confusing GCF with LCM and giving the multiple instead of the divisor, which produces a number much too large. The third is using subtraction in place of modulo in the Euclidean algorithm — the subtractive form works but is dramatically slower for inputs of different magnitudes (gcd(10⁹, 1) takes 10⁹ steps by subtraction, but only 1 step by modulo). The fourth is forgetting that GCF for negative numbers uses absolute values, so gcd(-12, 18) = 6, not -6 or some negative result. The fifth is computing GCF of non-integers — gcd(2.5, 1.5) is not defined in the standard sense, though it can be extended to rationals via lcm of denominators.
When should I not use this calculator?
Skip it for non-integer inputs — GCF is only defined on integers in the standard sense, and decimals or fractions need a different approach (gcd(p/q, r/s) = gcd(p·s, r·q) / (q·s) is one extension). Do not use it when you actually need the least common multiple; use an LCM calculator instead. It is the wrong tool for "GCF of three or more numbers" in one shot — you would have to chain it manually; multi-input GCD tools are more efficient. Avoid it for polynomial GCD (finding the largest polynomial that divides two given polynomials) — that needs polynomial long division, not integer modulo. Finally, do not use it for cryptographic-strength gcd on huge integers (used in RSA key generation) — those need a big-integer library, not a calculator widget; even though the algorithm is the same, the data types this calculator uses cannot represent the inputs.