Greatest Common Factor

Largest integer dividing both numbers.

First number

Second number

GCF

How to Use the GCF Calculator

Enter the first integer into the 'Number 1' field (e.g., 48).
Enter the second integer (or more numbers if additional fields are available) into the 'Number 2' field (e.g., 180).
Click the **Calculate** button.
The calculator instantly displays the GCF along with a step-by-step Euclidean algorithm breakdown.
Use the result to simplify fractions, factor expressions, or solve real-world division problems.

GCF Formula – Euclidean Algorithm

GCF(a, b) = GCF(b, a mod b), where GCF(a, 0) = a

The most efficient way to compute the GCF of two integers is the Euclidean Algorithm. It works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until the remainder reaches zero. The last non-zero remainder is the GCF.

For more than two numbers, apply the algorithm iteratively: GCF(a, b, c) = GCF(GCF(a, b), c).

a — The first positive integer (or the current larger value during iteration).
b — The second positive integer (or the current smaller value during iteration).
a mod b — The remainder when a is divided by b. This replaces 'a' in the next iteration step.
GCF(a, 0) = a — The base case: when the remainder reaches 0, the other number at that step is the Greatest Common Factor.

Worked Example: GCF of 48 and 180

a = 48, b = 180

Step 1: GCF(180, 48) → 180 mod 48 = 36 (since 180 = 3 × 48 + 36)
Step 2: GCF(48, 36) → 48 mod 36 = 12 (since 48 = 1 × 36 + 12)
Step 3: GCF(36, 12) → 36 mod 12 = 0 (since 36 = 3 × 12 + 0)
Remainder is 0, so the GCF is the last non-zero remainder.

Result: GCF(48, 180) = 12

What Your Result Means

The GCF of 48 and 180 is 12. This means 12 is the largest integer that divides both 48 and 180 evenly. For example, the fraction 48/180 simplifies to 4/15 by dividing both the numerator and denominator by 12.

Understanding GCF

What Is the Greatest Common Factor?

The Greatest Common Factor (GCF) — also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) — is the largest number that divides two or more integers exactly, with no remainder.

Why Does the GCF Matter?

Simplifying fractions: Divide both numerator and denominator by the GCF to reach the lowest terms.
Algebra: Factor polynomials by pulling out the GCF of the coefficients.
Real-world problems: Evenly split items into the largest possible equal groups (e.g., arranging 48 apples and 180 oranges into identical baskets).
Cryptography and computer science: The Euclidean algorithm underpins RSA encryption and many number-theory applications.

Methods for Finding the GCF

1. Euclidean Algorithm (Most Efficient)

Repeatedly take remainders until you reach zero. Fast even for very large numbers.

2. Prime Factorization

Break each number into prime factors, then multiply the common prime factors together.

48 = 2⁴ × 3
180 = 2² × 3² × 5
Common factors: 2² × 3 = 4 × 3 = 12 ✓

3. Listing Factors

List all factors of each number, identify the largest shared one. Practical only for small numbers.

GCF vs. LCM

The Least Common Multiple (LCM) is the smallest number that both integers divide into. GCF and LCM are related by:

GCF(a, b) × LCM(a, b) = a × b

For 48 and 180: 12 × LCM = 48 × 180 = 8,640, so LCM = 720.

Common Mistakes

**Confusing GCF with LCM:** GCF is the largest common *divisor*, while LCM is the smallest common *multiple*. They solve different problems.
**Using 1 as the answer by default:** While GCF(a, b) = 1 is possible (co-prime numbers), always run through the algorithm — the answer is often larger.
**Forgetting to apply GCF iteratively for 3+ numbers:** GCF(a, b, c) requires two separate GCF computations, not a single three-way step.
**Mixing up 'mod' with division:** 'a mod b' is the *remainder*, not the quotient. E.g., 180 mod 48 = 36, not 3.75.
**Entering non-integer or negative values:** GCF is defined for positive integers. Most calculators take the absolute value of negatives, but decimals are not valid inputs.

Common Questions About GCF

How is GCF used to simplify fractions?

To simplify a fraction a/b, divide both the numerator and denominator by GCF(a, b). For example, 36/48 simplifies to 3/4 because GCF(36, 48) = 12, and 36÷12 = 3, 48÷12 = 4.

What is the relationship between GCF and LCM?

For any two positive integers a and b: GCF(a, b) × LCM(a, b) = a × b. This formula lets you find the LCM quickly if you already know the GCF.

Can you find the GCF of decimals or fractions?

The standard GCF is defined for positive integers. For fractions p/q and r/s, the GCF can be defined as GCF(p,r)/LCM(q,s), but this is a specialized extension not used in everyday arithmetic.

Why is the Euclidean algorithm preferred over prime factorization for large numbers?

Prime factorization becomes computationally expensive for very large numbers (this difficulty actually underlies RSA cryptography). The Euclidean algorithm runs in O(log(min(a,b))) steps, making it dramatically faster for large integers.

Frequently Asked Questions

What is the difference between GCF and GCD?

GCF (Greatest Common Factor) and GCD (Greatest Common Divisor) are the same concept with different names. 'GCF' is more common in elementary and middle-school math, while 'GCD' is preferred in higher mathematics and computer science.

Can the GCF of two numbers ever be larger than either number?

No. The GCF of two positive integers can never exceed the smaller of the two numbers, because no factor of a number can be larger than the number itself.

What does it mean if GCF(a, b) = 1?

If the GCF equals 1, the two numbers are called **co-prime** (or relatively prime). They share no common factors other than 1. For example, GCF(8, 15) = 1.

How do I find the GCF of three or more numbers?

Apply the Euclidean algorithm iteratively. First compute GCF(a, b), then compute GCF(result, c), and so on. For example, GCF(12, 18, 24) = GCF(GCF(12, 18), 24) = GCF(6, 24) = 6.

Is the GCF of a number and 0 always the number itself?

Yes. By the base case of the Euclidean algorithm, GCF(a, 0) = a. So GCF(15, 0) = 15. This is consistent with the definition since every integer divides 0.

Related Calculators

LCM Calculator Percentage Calculator Exponent Calculator Factorial Calculator Modulo Calculator

Sources

Euclidean Algorithm – Khan Academy — Khan Academy
Greatest Common Divisor – Wolfram MathWorld — Wolfram MathWorld
CCSS.MATH.CONTENT.6.NS.B.4 – Common Core State Standards Initiative — Common Core State Standards Initiative

Only sources that have been reviewed are shown. Unverified citations are never published.

Spotted a calculation error?Report an Error