GCF Calculator
Greatest common factor by Euclid’s own algorithm: every division line printed, the full common-divisor list shown as exactly the divisors of the gcd, and the lcm delivered on the identity.
GCF Calculator
Results recalculate instantly on every keystroke. Nothing you type is transmitted.
What this result does not account for
- Two integers per run
- Positive whole numbers only — signs and zero are refused, not silently normalized
In short: gcd(48, 36) = 12 — Euclid in two lines: 48 = 1×36 + 12, then 36 = 3×12 + 0, and the last non-zero remainder is the answer. Every common divisor of 48 and 36 (1, 2, 3, 4, 6, 12) divides 12, and 12 divides itself — the gcd is the roof of its own divisor list. The identity closes the loop: 48 × 36 = 1,728 = 12 × 144.
Formula
a = q×b + r → repeat with (b, r)
r = 0 → the last non-zero remainder is the gcd
Euclid, Elements Book VII — about 300 BC, and still the fastest exact method in the room.
Worked Example
- Divide, keep the remainder. 48 = 1×36 + 12 — the gcd of 48 and 36 is also the gcd of 36 and 12, because anything dividing both 48 and 36 must divide their remainder 12.
- Slide down. repeat with the smaller pair: 36 = 3×12 + 0. The remainder hit zero — stop.
- Read the last non-zero remainder. 12. Every common divisor divides it, it divides itself, and the identity hands over the lcm: a × b = gcd × lcm.
One number dividing the other is the one-line case: gcd(12, 60) is found the moment 60 = 5×12 + 0. Coprime pairs end at 1 — gcd(17, 4): 17 = 4×4 + 1, 4 = 4×1 + 0 — and a gcd of 1 is the whole reason some fractions cannot be reduced.
Strengths & Limits Of This Model
Where this engine is strong
- Every Euclid line printed — the slide is auditable
- Common divisors derived as a theorem (divisors of the gcd), not enumerated by brute force
Where it stops
- No prime-factorization view
- No extended Euclid (no Bézout coefficients)
Practical Use Cases
Simplifying fractions
divide top and bottom by the gcd and the fraction is in lowest terms
Tiling and cutting
the largest square tile that grids both dimensions exactly
Scheduling
the longest slot that divides two period lengths with nothing left over
Methodology & Editorial Standards
Euclid’s algorithm on (a, b): while b ≠ 0, record a = q×b + r and slide to (b, r). The last non-zero remainder is the gcd; the common-divisor list is the gcd’s own divisor list; the lcm arrives by the identity and is printed in the a × b = gcd × lcm form. Both operands must be whole numbers of at least 1.
Computation runs in IEEE-754 double precision at full internal precision; rounding to two decimal places occurs strictly at the display layer, so no cumulative drift enters the result. All monetary outputs use accounting presentation — grouped thousands, two decimals, negatives in parentheses — so figures can be transcribed directly into a model or working paper. Division-by-zero and out-of-domain inputs return an em-dash rather than a misleading number.
This engine was reconciled against an independent reference implementation and hand-verified for the worked example above before release. Our full five-stage review process is published on the About Us page.
Disclaimer. This calculator is provided for informational and modelling purposes only and does not constitute financial, tax, legal, medical, or engineering advice. Verify all figures with a qualified professional before acting on them.
GCF Calculator — 9 Expert FAQs
9 analyst-written answers to the questions practitioners actually ask — optimised for voice and answer-engine retrieval.
What does the GCF (greatest common factor) mean?
The largest whole number that divides both inputs with nothing left over. For 48 and 36 that is 12: the common divisors are 1, 2, 3, 4, 6 and 12, and 12 is the roof. Everything the two numbers share, the gcd concentrates.
WHY does replacing (a, b) with (b, a mod b) never lose the gcd?
Because anything that divides both a and b also divides a − q×b = r, and anything that divides both b and r also divides a = q×b + r. The two pairs have exactly the same set of common divisors — same gcd, strictly smaller numbers. Euclid’s whole algorithm is that one observation, repeated until the remainder is zero.
Why is the last non-zero remainder the gcd?
The slide stops when the remainder hits 0, and each step preserves the common-divisor set. At the end the pair is (g, 0): every number divides 0, so the common divisors of (g, 0) are exactly the divisors of g — and the largest is g itself. The algorithm literally lands on its answer.
The gcd came out as 1 — what does that mean?
The two numbers are coprime: their only shared factor is 1. 17 and 4 get there in two lines. Practically, a fraction with gcd 1 between numerator and denominator is already in lowest terms — this is why 17/4 cannot be simplified no matter how you try.
Why does the page also print the lcm?
The identity a × b = gcd × lcm ties the two ends of the see-saw together, so computing one hands over the other for free: 48 × 36 = 1,728 = 12 × 144. It also doubles as a checksum — if the printed identity did not balance, the arithmetic would be lying, and it never balances wrong.
What are the common divisors themselves?
Exactly the divisors of the gcd — that is a theorem, not a coincidence. Anything dividing both 48 and 36 must divide their gcd 12, and everything dividing 12 divides both. So the list 1, 2, 3, 4, 6, 12 is read straight off the gcd’s own divisors, and the page prints it that way.
Is this the same as prime factorization?
It reaches the same answer by a different road. Factorization reads the SHARED primes (48 = 2⁴×3, 36 = 2²×3², so gcd = 2²×3 = 12) — great for seeing structure, slow for big numbers. Euclid never factors anything: he only takes remainders, which is why his method still wins at sizes where factorization has given up.
When is the algorithm at its fastest and slowest?
Slowest is one step off the Fibonacci pairs — consecutive Fibonacci numbers force the maximum number of remainder lines for their size. Fastest is the one-line case where one number divides the other: gcd(12, 60) is over the instant 60 = 5×12 + 0. Either way the line count stays tiny — the number of lines grows like the logarithm of the smaller input.
Do negatives or zero belong here?
No, and the refusal is honest rather than fussy. Signs are decoration for divisibility — gcd(−48, 36) is defined as gcd(48, 36) — and gcd(0, n) = n is a boundary convention, not a calculation. The page asks for the positives so every printed line stays inside the division story that proves it.