Loading…
Find the greatest common factor of two whole numbers using the Euclidean algorithm.
Find the greatest common factor of two whole numbers using the Euclidean algorithm.
Enter values above and click Calculate — results will appear here with the formula explained.
The greatest common factor (also called GCD or HCF) is the largest whole number that divides both inputs without a remainder. It is what you divide by to reduce a fraction: 48/36 reduces to 4/3 because GCF = 12. The same number also tells the largest tile, group or batch that fits evenly into both quantities — hence its constant use in simplifying ratios, splitting resources and aligning repeating cycles.
The Euclidean algorithm finds it without factoring: keep replacing the pair (a, b) with (b, a mod b). The remainders shrink quickly, and the last non-zero remainder is the answer — remarkably efficient even for enormous numbers. Euclid proved this around 300 BCE and it remains the fastest general method, running in logarithmic time.
Why not just list factors? Listing all divisors of 1,000,000 takes hundreds of divisions; Euclid needs about five steps for the same pair. For 1071 and 462 the sequence is 1071 mod 462 = 147, 462 mod 147 = 21, 147 mod 21 = 0 — three steps to GCF 21. That gap widens into orders of magnitude as numbers grow, which is why every computer algebra system uses Euclid under the hood.
GCF and LCM are linked by GCF × LCM = a × b. Once you have the GCF, the least common multiple is one multiplication away: LCM(48, 36) = 48 × 36 ÷ 12 = 144. That identity is how this calculator shows both results from a single Euclid run, and why reducing a fraction and finding a common denominator are two sides of the same number.
Properties worth remembering: consecutive integers always have GCF 1 (no factor greater than 1 can divide neighbors), a multiple inherits the smaller number as GCF — GCF(6, 18) = 6 — and scaling both inputs scales the GCF equally: GCF(100, 60) = 20 implies GCF(1000, 600) = 200. Coprime numbers are defined as GCF 1, the condition that makes a fraction already reduced.
Practical uses extend beyond arithmetic class: simplifying aspect ratios (1920:1080 → divide by GCF 120 → 16:9), packing problems (largest equal-size boxes that fit two inventories), cryptography where coprimality underpins RSA, and music where GCF governs how many beats align two rhythms. Anywhere two counts must be divided into equal groups without remainder, GCF is the governing number. In project planning, GCF also determines the largest equal squad size that partitions two teams without leftovers — the same arithmetic that makes 48 and 36 split cleanly into 12 also splits 120 engineers and 90 designers into 30-person pods of 4 and 3.
Find the greatest common factor of two whole numbers using the Euclidean algorithm.
The greatest common factor (also called GCD or HCF) is the largest whole number that divides both inputs without a remainder. It is what you divide by to reduce a fraction: 48/36 reduces to 4/3 because GCF = 12. The same number also tells the largest tile, group or batch that fits evenly into both quantities — hence its constant use in simplifying ratios, splitting resources and aligning repeating cycles.
The Euclidean algorithm finds it without factoring: keep replacing the pair (a, b) with (b, a mod b). The remainders shrink quickly, and the last non-zero remainder is the answer — remarkably efficient even for enormous numbers. Euclid proved this around 300 BCE and it remains the fastest general method, running in logarithmic time.
Why not just list factors? Listing all divisors of 1,000,000 takes hundreds of divisions; Euclid needs about five steps for the same pair. For 1071 and 462 the sequence is 1071 mod 462 = 147, 462 mod 147 = 21, 147 mod 21 = 0 — three steps to GCF 21. That gap widens into orders of magnitude as numbers grow, which is why every computer algebra system uses Euclid under the hood.
GCF and LCM are linked by GCF × LCM = a × b. Once you have the GCF, the least common multiple is one multiplication away: LCM(48, 36) = 48 × 36 ÷ 12 = 144. That identity is how this calculator shows both results from a single Euclid run, and why reducing a fraction and finding a common denominator are two sides of the same number.
Properties worth remembering: consecutive integers always have GCF 1 (no factor greater than 1 can divide neighbors), a multiple inherits the smaller number as GCF — GCF(6, 18) = 6 — and scaling both inputs scales the GCF equally: GCF(100, 60) = 20 implies GCF(1000, 600) = 200. Coprime numbers are defined as GCF 1, the condition that makes a fraction already reduced.
Practical uses extend beyond arithmetic class: simplifying aspect ratios (1920:1080 → divide by GCF 120 → 16:9), packing problems (largest equal-size boxes that fit two inventories), cryptography where coprimality underpins RSA, and music where GCF governs how many beats align two rhythms. Anywhere two counts must be divided into equal groups without remainder, GCF is the governing number. In project planning, GCF also determines the largest equal squad size that partitions two teams without leftovers — the same arithmetic that makes 48 and 36 split cleanly into 12 also splits 120 engineers and 90 designers into 30-person pods of 4 and 3.
GCF(48, 36): 48 mod 36 = 12, then 36 mod 12 = 0, so the GCF is 12. Reducing 48/36 by 12 gives 4/3. A ratio example: 1920×1080 simplifies by GCF 120 to 16:9 — divide both sides by 120. A packing example: 48 apples and 36 oranges split into largest equal boxes: 12 per box gives 4 apple-boxes and 3 orange-boxes.
Formulas are standard public references (see our methodology). External standards are cited in the text where they apply.
Last reviewed: September 2026 · Report an error