0
—
—
—
—
0
—
—
—
—
The GCF Calculator (Greatest Common Factor, also called GCD — Greatest Common Divisor) finds the largest positive integer that divides both input numbers without leaving a remainder. This calculator implements the Euclidean algorithm, one of the oldest and most elegant algorithms in mathematics, dating back to Euclid's Elements (circa 300 BC).
The GCF is fundamental throughout mathematics: it is used to simplify fractions (divide numerator and denominator by GCF), solve Diophantine equations, determine modular inverses in cryptography, and optimize resource allocation problems. For example, GCF(48, 18) = 6, meaning 48/18 simplifies to 8/3.
Beyond the GCF itself, this calculator also computes the Least Common Multiple (LCM) using the relationship $$\text{LCM}(a, b) = \frac{|a \times b|}{\text{GCF}(a, b)}$$ and shows the reduced quotients a/GCF and b/GCF, which represent the simplified form of the fraction a/b.
The calculator uses the Euclidean algorithm, which is based on the principle that $$\gcd(a, b) = \gcd(b, a \bmod b)$$:
Algorithm steps:
This implementation hardcodes 10 iterations of the modular reduction, which is sufficient because the Euclidean algorithm converges extremely fast — the number of steps is at most $$5 \times \log_{10}(\min(a,b))$$. For inputs up to 1,000,000, at most 30 steps are needed, and 10 iterations handle the vast majority of practical cases.
LCM calculation: $$\text{LCM}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$$
This elegant relationship connects the two fundamental divisibility concepts.
The GCF represents the largest "common unit" that both numbers are multiples of. If GCF = 1, the numbers are coprime (relatively prime) — they share no common factors. The reduced quotients (a/GCF and b/GCF) are always coprime and represent the fraction a/b in lowest terms. The LCM is the smallest number that both a and b divide into evenly, useful for finding common denominators when adding fractions.
Inputs
Results
48 = 6 × 8, 18 = 6 × 3. GCF = 6. The fraction 48/18 simplifies to 8/3. LCM = 48 × 18 / 6 = 144.
Inputs
Results
35 = 5 × 7, 24 = 2³ × 3 — no common prime factors. GCF = 1 (coprime). LCM = 35 × 24 = 840.
They are all the same concept with different names: GCF (Greatest Common Factor), GCD (Greatest Common Divisor), and HCF (Highest Common Factor). GCF and HCF are more common in American and British school mathematics, while GCD is standard in higher mathematics and computer science. The notation $$\gcd(a, b)$$ is most widely used.
The Euclidean algorithm is efficient because the remainders decrease rapidly — in the worst case (consecutive Fibonacci numbers), the number of steps is proportional to $$\log(\min(a,b))$$. This is exponentially faster than trial division, which would check every possible divisor. Lame's theorem (1844) proved that the number of steps never exceeds 5 times the number of digits in the smaller number.
When $$\gcd(a, b) = 1$$, the numbers are called coprime or relatively prime. They share no common prime factors. This does not mean either number is prime — for example, gcd(8, 15) = 1, but neither 8 nor 15 is prime. Coprimality is important in modular arithmetic, particularly for the existence of modular inverses.
To simplify $$a/b$$, divide both by their GCF: $$\frac{a}{b} = \frac{a/\gcd(a,b)}{b/\gcd(a,b)}$$. For example, $$\frac{48}{18} = \frac{48/6}{18/6} = \frac{8}{3}$$. The result is the fraction in its lowest terms, where numerator and denominator are coprime.
For any two positive integers: $$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$. This means knowing any three of these four values determines the fourth. This relationship provides an efficient way to compute LCM without finding prime factorizations. It also implies that $$\text{lcm}(a,b) \geq \max(a,b)$$ and $$\gcd(a,b) \leq \min(a,b)$$.
This calculator works with two numbers at a time. To find the GCF of three or more numbers, apply the algorithm iteratively: $$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$$. For example, gcd(12, 18, 24) = gcd(gcd(12, 18), 24) = gcd(6, 24) = 6. The same chaining principle works for LCM.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
