GCF / GCD Calculator

Find the Greatest Common Factor (GCF, also called GCD) of 2 to 5 numbers. See the complete Euclidean algorithm step by step and the LCM.

Enter 2 to 5 positive integers.

What is the Greatest Common Factor?

The Greatest Common Factor (GCF), also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest positive integer that divides each of two or more integers without a remainder. For example, the GCF of 12 and 18 is 6, because 6 is the largest number that divides evenly into both 12 (12÷6=2) and 18 (18÷6=3). The GCF of a set of numbers is found by identifying all common factors and selecting the largest one — or more efficiently, by applying the Euclidean Algorithm, which repeatedly takes the remainder of division until reaching zero.

The Euclidean Algorithm, attributed to the ancient Greek mathematician Euclid (~300 BCE) and described in his work Elements, is one of the oldest known algorithms still in widespread use. It works by the observation that GCF(a, b) = GCF(b, a mod b): the GCF of two numbers equals the GCF of the smaller number and the remainder when the larger is divided by the smaller. Repeating this substitution until the remainder is zero yields the GCF in the final non-zero remainder. For example: GCF(48, 18) → GCF(18, 12) → GCF(12, 6) → GCF(6, 0) = 6.

The GCF has a natural partner: the Least Common Multiple (LCM), found using the relationship LCM(a, b) = (a × b) / GCF(a, b). Together, GCF and LCM are fundamental tools in fraction arithmetic (for finding common denominators), number theory, cryptography, and computer science. The GCF is used to reduce fractions to lowest terms; the LCM is used to find the smallest common denominator when adding or comparing fractions. This calculator finds the GCF of up to five numbers simultaneously, shows the complete Euclidean Algorithm steps, and also computes the LCM.

Euclidean Algorithm

The Euclidean algorithm finds GCF by repeatedly applying: GCF(a, b) = GCF(b, a mod b), until the remainder is 0.

GCF(48, 18):

48 = 18 × 2 + 12 → GCF(18, 12)

18 = 12 × 1 + 6 → GCF(12, 6)

12 = 6 × 2 + 0 → GCF = 6

How the GCF Calculator Works

Formula, assumptions, and calculation steps for this math tool.

Methodology

Math calculators apply the relevant arithmetic, algebraic, geometric, or numeric rule to the values entered and simplify the result where possible.

Calculation Steps

Read the values and operation selected.
Normalize signs, decimals, fractions, or units if needed.
Apply the mathematical rule or formula.
Format the answer and any intermediate values for checking.

Assumptions and Limits

Inputs must be within the supported domain of the operation.
Decimal answers may be rounded for readability.
Symbolic simplification is limited to the calculator scope.

Frequently Asked Questions

What is GCF?

The Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD), is the largest positive integer that divides all given numbers without a remainder.

What is the Euclidean algorithm?

An efficient algorithm to compute GCF: divide the larger number by the smaller and take the remainder. Repeat with the smaller number and the remainder until the remainder is zero. The last non-zero remainder is the GCF.

What does GCF = 1 mean?

If GCF(a, b) = 1, the numbers are called coprime or relatively prime. They share no common prime factors. For example, GCF(8, 9) = 1.

How is GCF used in simplifying fractions?

To simplify a fraction a/b, divide both numerator and denominator by GCF(a, b). For example, 12/18 → GCF = 6 → 2/3.

Can GCF be larger than one of the numbers?

No. The GCF is always less than or equal to the smallest of the given numbers, since a common factor must divide all numbers, and no number can have a divisor larger than itself (except in trivial cases).

Real-World Applications

➗

Simplifying Fractions

Divide numerator and denominator by their GCF to reduce a fraction to its lowest terms — e.g. 48/72 ÷ 24 = 2/3.

🗓️

Event Scheduling

Find when two recurring events coincide using LCM — if event A recurs every 12 days and event B every 18 days, they next meet in LCM(12,18) = 36 days.

🔵

Tile Pattern Design

Find the largest square tile that evenly covers a floor of dimensions 240 cm × 360 cm — the GCF(240,360) = 120 cm.

📐

Material Cutting

Determine the longest equal-length pieces that can be cut from two different-length rods without any waste using GCF of their lengths.

🔐

Cryptography

The Euclidean Algorithm is the basis for extended GCD, used in RSA key generation and modular inverse computation.

📦

Packing Problems

Find the largest equal-sized groups that can be formed from two quantities — e.g. packing 24 apples and 36 oranges into equal-sized baskets with no leftovers.

Common Mistakes

Listing factors only to find common ones

While listing all factors works for small numbers, the Euclidean Algorithm is far more efficient for large numbers — GCF(2024, 1768) would require listing many factors.

Confusing GCF with LCM

GCF is the LARGEST number that divides both; LCM is the SMALLEST number that both divide into. For 4 and 6: GCF = 2, LCM = 12.

Thinking GCF(a,0) = 0

By convention, GCF(a,0) = a for any positive integer a. Zero has every positive integer as a divisor, so the greatest common factor of a and 0 is a itself.

Not using GCF before LCM

Computing LCM(a,b) = a×b / GCF(a,b) is more accurate than trying to list multiples — especially for large numbers where the list is impractically long.

Treating GCF of primes as non-trivial

The GCF of any two different prime numbers is always 1 — they share no common factors other than 1. GCF(7, 13) = 1, making them coprime.

GCF and LCM Quick Reference

Numbers (a, b)	GCF	LCM	GCF × LCM = a × b
12, 18	6	36	6 × 36 = 216 = 12 × 18 ✓
24, 36	12	72	12 × 72 = 864 = 24 × 36 ✓
7, 13 (both prime)	1	91	1 × 91 = 91 = 7 × 13 ✓
100, 75	25	300	25 × 300 = 7,500 = 100 × 75 ✓
48, 64	16	192	16 × 192 = 3,072 = 48 × 64 ✓

References

Euclid. Elements, Book VII. ~300 BCE (translated by Heath, 1956).
Hardy, G.H. and Wright, E.M. An Introduction to the Theory of Numbers. Oxford University Press, 2008.
Knuth, Donald. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley, 1997.
National Council of Teachers of Mathematics. Principles and Standards for School Mathematics. NCTM, 2000.
Rivest, R., Shamir, A., Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." Communications of the ACM, 1978.