48 × 180 = 8,640, and 12 × 720 = 8,640 — the same number. For a pair, the greatest common factor times the least common multiple is the product.
Euclid and the prime route are computed separately and must agree before anything above is shown.
What this tool shows
The divisor is computed twice, by unrelated methods, and both are shown: the shared primes explain it, Euclid finds it in a handful of lines on numbers far too large to factorise by hand.
The greatest common factor of two to six numbers
Euclid’s algorithm with every line shown
The shared primes, each to its lower power
Every factor of each number, when they are small enough
The fraction the answer reduces
The identity linking it to the least common multiple
Euclid, line by line Shared primes, lower powers Up to six numbers at once The fraction it reduces
Updated 7 September 2026 · Works in any browser, no installation
The greatest common factor of two numbers is the largest number that divides both. Find it by taking the primes they share, each to the LOWER of its two powers — or by Euclid’s algorithm, which repeatedly replaces the larger number by the remainder until nothing is left. 48 and 180 share 2² and 3, so the answer is 12, and 48/180 reduces to 4/15 in one step.
At a glance
Formula shown
gcd(a, b) = gcd(b, a mod b), repeated until the remainder is zero; the last non-zero remainder is the answer. By primes: the product of every shared prime raised to the lower of its powers. For three or more, fold pairwise.
Scenario support
Reducing a fraction to lowest terms; splitting two quantities into equal groups of the largest possible size; finding the biggest tile that fits a room exactly in both directions.
Educational estimate
Planning support from the values you enter — not professional advice.
Three methods, and when each fails
Listing every factor and picking the largest common one is the method that makes the definition obvious, and it is the first to become impossible. It is shown here whenever every input is small enough for the list to be readable, and skipped with a note when it is not — truncating a list silently would be worse than omitting it.
Prime factorisation explains the answer. Once both numbers are written as primes, the shared part is read straight off. It stops being practical when the numbers get large, because factorising is hard even though this particular question is not.
Euclid’s algorithm never factorises anything and finishes in a handful of lines regardless of size. It is what every computer algebra system uses, and it works on numbers nobody could factorise at all.
Euclid, and why it is still used
The whole algorithm is one observation: any number dividing both a and b also divides their remainder. So the pair (a, b) can be replaced by (b, a mod b) without changing the answer, and the numbers shrink fast.
1071 and 462 takes three lines. 1071 = 2 × 462 + 147, then 462 = 3 × 147 + 21, then 147 = 7 × 21 + 0. The last non-zero remainder, 21, is the answer.
The number of steps grows only with the number of DIGITS, not the size — the worst case is consecutive Fibonacci numbers, and even those take about five steps per digit. That is why an algorithm from around 300 BC is still the one in the library you are using right now.
The lower power, not the higher
This is the step that gets reversed. When 48 is 2⁴ × 3 and 180 is 2² × 3² × 5, the shared part is 2² × 3, not 2⁴ × 3².
The reason is simple once said aloud: you can only take out as many twos as the SHORTER side has. 180 only has two of them, so two is all that can come out of both. Taking the higher power would produce a number that does not divide 180 at all.
It is also exactly the rule that reverses for the least common multiple, where you take the higher power of every prime that appears anywhere. Same table, opposite instruction — and the two pages are worth reading together for that reason.
Coprime is an answer
When the greatest common factor is 1, the numbers are coprime. That is not a failure to find something; it is a useful fact with several immediate consequences.
A fraction built from them is already in lowest terms. Their least common multiple is simply their product, with no overlap to remove. And in modular arithmetic, coprimality is exactly the condition for an inverse to exist — which is why it underpins RSA.
Two different primes are always coprime, but so are 8 and 9, which are not prime at all. Sharing no factor is a relationship between numbers rather than a property of either one.
GCF × LCM = the product
For a pair, the greatest common factor and the least common multiple multiply to give the product of the two numbers. 12 × 18 = 216, and gcd 6 times lcm 36 is also 216.
So finding either gives the other for free, and the cheap direction is the GCF — Euclid is fast, and the least common multiple then follows by dividing. That is exactly how the LCM is computed on this site.
The identity holds only for a PAIR. For three or more it fails: gcd(2, 3, 4) is 1 and lcm(2, 3, 4) is 12, but the product is 24. Fold pairwise instead.
What it is actually for
Reducing fractions. The commonest use by far. Divide the numerator and denominator by their greatest common factor and the fraction is in lowest terms in one step.
Equal groups. Given 48 of one thing and 180 of another, the largest set of identical bundles you can make is 12 — each with 4 and 15 in it. The bundle count is the GCF and the contents are the reduced fraction.
Tiling and cutting. The largest square tile that fits a 48 by 180 floor with no cutting is 12 across, for exactly the same reason.
Simplifying ratios. A 48:180 mix is a 4:15 mix, which is the form anyone can actually work with.
Sources and methodology
Euclid’s algorithm is about two and a half thousand years old and unchanged. These are where it and the conventions are set out.
Method. The divisor is folded pairwise with Euclid’s algorithm, which takes remainders and never factorises, and every line of that fold is recorded. Separately each number is factorised by trial division and the primes present in all of them are taken to their lowest powers. The two are compared before anything is shown. Factor lists are produced only when every input is small enough for the list to be honest; past that the page says it has stopped rather than truncating quietly. That engine is verified on every change against 64 hand-written assertions, including that gcd × lcm equals the product for every pair up to 120 × 120, and that the reported divisor divides every input. The count and the per-case breakdown are published on the formula verification page.
Related calculators
Where this goes next:
LCMThe least common multiple of two to six numbers, with the prime table that produces it, the multiples themselves, and how far counting would have had to go.
Simplify FractionsReduce a fraction to lowest terms with both routes to the divisor shown side by side — Euclid line by line and the shared primes — and a stated proof when nothing can be cancelled.
Prime FactorizationBreak any number into primes with the division ladder shown, the number of trial divisions reported, and the argument for why the search can stop at the square root.
FactorEvery factor of a number listed in the pairs that generate them, with the count derived from the prime exponents and separately checked against the list.
FractionAdd, subtract, multiply and divide fractions and mixed numbers exactly, with the least common denominator chosen, the cross-cancelling done first, and the true repeating decimal beside the answer.
Divisibility TestEvery divisibility rule from 2 to 16 applied to your number, each with its working, the reason it holds, and the true remainder beside it as a check.
The mirror question — what covers both rather than what they share — is the LCM Calculator, and for a pair the two answers determine each other. If what you actually wanted was to reduce a fraction, the Simplify Fractions Calculator does that with the same two routes shown.
Educational use disclaimer
This is an educational tool. The divisor is exact and computed by two independent methods that must agree, but the presentation follows one common teaching order — your course may lay the same working out differently.