🔵Greatest Common Factor Calculator
Find the greatest common factor (GCF), also called greatest common divisor (GCD), of two or more integers. Uses the Euclidean algorithm with BigInt for arbitrary precision. Also shows prime factorizations and step-by-step workings.
Prefer to skip the form? Scroll down and Ask AI Instead. Just describe your situation and let AI handle the math for you in seconds.
Greatest Common Factor
15
Input Numbers vs GCF
✦ Ask AI Instead
Greatest Common Factor Calculator: GCF, GCD, and HCF Explained
The greatest common factor (GCF) — also called greatest common divisor (GCD) or highest common factor (HCF) — is the largest positive integer that divides each of the given numbers without leaving a remainder. GCF(48, 72) = 24 because 24 divides both 48 and 72, and no larger number does.
Euclidean Algorithm: GCF(a, b) = GCF(b, a mod b) repeated until remainder = 0
| Numbers | Prime Factorization | GCF |
|---|---|---|
| 48, 72 | 2⁴×3, 2³×3² | 24 = 2³×3 |
| 330, 75, 450 | 2×3×5×11, 3×5², 2×3²×5² | 15 = 3×5 |
| 13, 17 | 13 (prime), 17 (prime) | 1 (coprime) |
Our greatest common factor calculator uses the Euclidean algorithm on BigInt, which means it handles arbitrarily large integers with exact arithmetic — no floating-point errors. You can enter two or more numbers separated by commas, and the calculator will find their GCF along with prime factorizations and step-by-step Euclidean workings.
Three Methods to Find the GCF
There are three standard methods for computing the GCF:
1. Listing factors: For small numbers, list all factors of each number and identify the largest one they share. Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24. Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. Common factors: 1, 2, 3, 4, 6, 12. GCF = 12. Simple but slow for large numbers.
2. Prime factorization: Express each number as a product of prime powers. The GCF equals the product of all primes appearing in every factorization, raised to the minimum exponent. For 360 = 2³×3²×5 and 540 = 2²×3³×5: GCF = 2²×3²×5 = 180. Elegant but factoring large numbers is computationally hard.
3. Euclidean algorithm: The fastest method. Relies on GCF(a, b) = GCF(b, a mod b). Works for any size number and converges in O(log min(a,b)) steps. For large numbers (millions of digits), it's the only practical approach — the Euclidean algorithm terminates in at most 5 times the number of decimal digits of the smaller input.
Why the GCF Matters
The GCF has applications across mathematics and everyday problem-solving. Simplifying fractions: 18/24 simplified = (18÷6)/(24÷6) = 3/4, where 6 = GCF(18, 24). Dividing things evenly: if you have 48 apples and 72 oranges to pack into identical bags with no leftovers, each bag can hold exactly GCF(48, 72) = 24 pieces. In algebra, factoring polynomials uses GCF to extract common terms. In cryptography, coprime numbers (GCF = 1) are essential for RSA key generation.
Coprime Numbers
Two numbers are coprime (or relatively prime) if their GCF is 1, meaning they share no prime factors. Example: 8 = 2³ and 15 = 3×5 are coprime because GCF(8, 15) = 1. Coprimality is fundamental in number theory. Euler's totient function φ(n) counts integers up to n that are coprime to n. Chinese Remainder Theorem works only when the moduli are pairwise coprime. Consecutive integers are always coprime: GCF(n, n+1) = 1 for all n.
Frequently Asked Questions
What is the difference between GCF, GCD, and HCF?
They are all the same concept with different names. GCF (Greatest Common Factor) is common in American elementary education. GCD (Greatest Common Divisor) is the standard mathematical term, widely used in number theory, algebra, and computer science. HCF (Highest Common Factor) is the British and Commonwealth equivalent of GCF. All three refer to the largest positive integer that divides each of the given numbers without a remainder. This calculator accepts any input and computes the GCF/GCD/HCF using the Euclidean algorithm.
How do I find the GCF of more than two numbers?
Apply the GCF operation iteratively: GCF(a, b, c) = GCF(GCF(a, b), c). For 12, 18, and 24: GCF(12, 18) = 6; GCF(6, 24) = 6. So GCF(12, 18, 24) = 6. This works because of the associative property of GCF. Equivalently, you can use prime factorization: find the prime factorization of each number and take the product of all common primes raised to the minimum exponent appearing across all factorizations. This calculator handles up to any number of inputs automatically.
What does it mean when the GCF equals 1?
When GCF(a, b) = 1, the numbers are called coprime or relatively prime — they share no common prime factors. Examples: GCF(8, 15) = 1 (8 = 2³, 15 = 3×5 — no shared primes); GCF(7, 11) = 1 (both prime, different primes). Coprime pairs are important in cryptography (RSA encryption), fraction arithmetic (a fraction a/b is in lowest terms when GCF(a, b) = 1), and number theory (basis for Euler's theorem and Chinese Remainder Theorem).
How does the Euclidean algorithm work step by step?
The Euclidean algorithm uses the identity GCF(a, b) = GCF(b, a mod b). Example — GCF(330, 75): Step 1: 330 = 75 × 4 + 30, so GCF(330, 75) = GCF(75, 30). Step 2: 75 = 30 × 2 + 15, so GCF(75, 30) = GCF(30, 15). Step 3: 30 = 15 × 2 + 0, so GCF(30, 15) = 15. Answer: GCF(330, 75) = 15. The algorithm terminates when the remainder is 0; the GCF is the last non-zero remainder. It converges extremely fast — for two n-digit numbers, it needs at most about 5n divisions.
Can I use the GCF to simplify fractions?
Yes — dividing numerator and denominator by their GCF gives the simplest form. For 48/72: GCF(48, 72) = 24; simplified = (48÷24)/(72÷24) = 2/3. For 330/450: GCF(330, 450) = 30; simplified = 11/15. A fraction a/b is in lowest terms if and only if GCF(a, b) = 1. The GCF method is more efficient than listing factors for large fractions: GCF(2310, 3465) = 1155 in just a few Euclidean steps, giving simplified fraction 2/3.