What is the Greatest Common Factor (GCF)?

The GCF, also called GCD or HCF, is the largest positive integer that divides all given numbers evenly. Example: GCF(12, 18) = 6, because 6 is the largest number that divides both.

What is the Euclidean algorithm for finding GCF?

GCF(a, b) = GCF(b, a mod b). Repeat until the remainder is 0; the last non-zero remainder is the GCF. Example: GCF(48, 18) → GCF(18, 12) → GCF(12, 6) → GCF(6, 0) = 6.

How do you find GCF using prime factorization?

1) Find the prime factorization of each number. 2) Identify common prime factors. 3) Multiply the lowest powers of those common primes. Example: 12 = 2² × 3 and 18 = 2 × 3², common = 2¹ × 3¹ = 6.

What is the relationship between GCF and LCM?

GCF(a, b) × LCM(a, b) = a × b, so LCM = (a × b) / GCF. Example: GCF(12, 18) = 6, so LCM(12, 18) = (12 × 18) / 6 = 36.

How do you find GCF of more than two numbers?

Compute pairwise: GCF(a, b, c) = GCF(GCF(a, b), c), and so on. Example: GCF(12, 18, 24) = GCF(GCF(12, 18), 24) = GCF(6, 24) = 6.

Greatest Common Factor Calculator - GCF

Understanding Greatest Common Factor

What is GCF?

The Greatest Common Factor (GCF), also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without leaving a remainder. It represents the largest number that can evenly divide all given numbers.

Mathematical Definition

For integers a, b, and d (where d ≠ 0), d is a common divisor if d divides a and d divides b. The greatest common divisor is the largest such positive integer.

\text{GCF}(a, b) = \max\{d \in \mathbb{N} \mid d|a \land d|b\}

Alternative Definition

The GCF can also be defined as the largest positive integer d such that a = d×m and b = d×n for some integers m and n.

d = \text{GCF}(a, b) \implies a = d \cdot m, b = d \cdot n \text{ for some } m, n \in \mathbb{Z}

Common Calculation Methods

Euclidean Algorithm

An efficient method using repeated division and remainders based on the property that $\text{GCF}(a, b) = \text{GCF}(b, a \bmod b)$

\text{GCF}(48, 18) = \text{GCF}(18, 48 \bmod 18) = \text{GCF}(18, 12)

\text{GCF}(18, 12) = \text{GCF}(12, 18 \bmod 12) = \text{GCF}(12, 6)

\text{GCF}(12, 6) = \text{GCF}(6, 12 \bmod 6) = \text{GCF}(6, 0) = 6

Prime Factorization

Factor each number into primes, then take the product of the lowest power of common primes

48 = 2^4 \times 3^1, 18 = 2^1 \times 3^1

\text{Common factors: } 2^1 \times 3^1 = 6

List Method

List all divisors of each number and find the greatest common one (works for small numbers)

Mathematical Foundations

Fundamental Theorem

Bezout's Identity: For any integers a and b, there exist integers x and y such that:

a \cdot x + b \cdot y = \text{GCF}(a, b)

This shows that the GCF can always be expressed as a linear combination of the original numbers.

Algorithm Efficiency

The Euclidean algorithm has logarithmic time complexity O(log min(a,b)). Each step reduces the problem size by at least half.

For numbers up to 10¹⁸, the algorithm completes in less than 60 steps.

Prime Factorization Theorem

Every positive integer greater than 1 can be uniquely expressed as a product of prime numbers. For GCF calculation:

a = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}, \quad b = p_1^{b_1} \times p_2^{b_2} \times \cdots \times p_k^{b_k}

\text{GCF}(a, b) = p_1^{\min(a_1,b_1)} \times p_2^{\min(a_2,b_2)} \times \cdots \times p_k^{\min(a_k,b_k)}

48 Cookies. 36 Brownies. One Annoying Problem.

You're packing party bags. Each bag gets some cookies and some brownies. Every bag must be identical. No leftovers. What's the maximum number of bags you can make?

The answer is 12. And the thing that gets you there — GCF — also happens to be what keeps your bank account secure. Not an exaggeration.

What GCF Actually Means

A factor is any number that divides evenly into another. Factors of 12: 1, 2, 3, 4, 6, 12. Factors of 8: 1, 2, 4, 8.

Common factors of 12 and 8 — numbers in both lists: 1, 2, 4. The greatest of those is 4.

So GCF(12, 8) = 4. The largest number that divides into both without a remainder.

GCF and GCD (Greatest Common Divisor) mean the same thing. Mathematicians say GCD. Teachers say GCF. Same calculation either way.

Back to the cookies: GCF(48, 36) = 12. That's how many bags you can make — 4 cookies and 3 brownies each, nothing left over.

Three Ways to Find It

Method 1: List the Factors (Fine for Small Numbers)

Write out every factor of each number. Find what they share. Take the biggest.

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36

Common: 1, 2, 3, 4, 6, 12 → GCF = 12

Tedious. Falls apart fast when numbers get larger. But it builds intuition.

Method 2: Prime Factorization

Break each number into primes. GCF is the product of shared prime factors.

GCF(360, 252)

$360 = 2^3 \\times 3^2 \\times 5$

$252 = 2^2 \\times 3^2 \\times 7$

Shared: $2^2$ and $3^2$

$GCF = 4 \\times 9 = 36$

More systematic. Still annoying for large numbers — factoring 3,654,921 by hand is not something anyone should do.

Method 3: Euclid's Algorithm (What Computers Actually Use)

This one is 2,300 years old and still faster than anything else. The key insight: GCF(a, b) = GCF(b, a mod b). Keep replacing until the remainder hits zero.

GCF(360, 252) via Euclid

360 = 1 × 252 + 108

252 = 2 × 108 + 36

108 = 3 × 36 + 0

Remainder = 0 → GCF = 36 ✓

Three steps. Same answer. And it works just as fast on numbers with 200 digits.

GCF Secures Your Bank Account

RSA encryption — the math behind HTTPS, the padlock in your browser, every secure login — depends on a property that comes directly from GCF.

The setup: RSA works by finding two huge primes (each ~300 digits long) and multiplying them together. Anyone can see the product. Nobody can factor it back into the original primes in any reasonable timeframe.

The security comes from the fact that Euclid's algorithm is fast at finding GCF — but factoring large numbers is brutally slow. When you log into your bank, your browser and the server exchange public keys and use GCF-based operations to establish a shared secret. An eavesdropper who sees the traffic would need to factor a 600-digit number. Current estimates: longer than the age of the universe with every computer on Earth working on it.

Two numbers with GCF = 1 are called coprime. RSA encryption specifically requires that the public key exponent and a derived value called φ(n) are coprime — GCF = 1. The algorithm checks this using Euclid's method, same one you just used on 360 and 252.

Where Else GCF Shows Up

Beyond fractions and cryptography:

Scheduling. Two buses run routes of 12 minutes and 8 minutes. When do they align at the same stop again? Every GCF(12,8) = 4 minutes. The related concept — LCM — tells you when cycles sync. GCF and LCM are two sides of the same idea: $\\text{GCF}(a,b) \\times \\text{LCM}(a,b) = a \\times b$
Tiling. Covering a 360cm × 252cm floor with square tiles, no cutting — the largest possible tile is 36cm × 36cm. GCF(360, 252) = 36.
Reducing fractions. $\\frac{252}{360} = \\frac{252 \\div 36}{360 \\div 36} = \\frac{7}{10}$ . That's the actual use case most people learned — and it's the least interesting application.

Quick Questions

GCF of two prime numbers?

Always 1. Primes have no factors other than 1 and themselves. Two different primes share only 1. GCF(7, 13) = 1. These are called coprime, or relatively prime.

Can GCF be larger than both numbers?

No. GCF(a, b) ≤ the smaller of the two. If one divides the other evenly, GCF equals the smaller one: GCF(12, 36) = 12.

GCF of three or more numbers?

Apply Euclid's algorithm in pairs: GCF(a, b, c) = GCF(GCF(a, b), c). Find the first two, then take GCF of that result with the third. Works for any number of inputs.

Find Any GCF Instantly

Enter two or more numbers. See GCF, LCM, and the full Euclid's algorithm step-by-step.

*Works for integers of any size. Uses Euclid's algorithm internally.

Greatest Common Factor Calculator

Number Theory

Algebra

Computer Science

Engineering