GCF Calculator (Greatest Common Factor)
Calculate the Greatest Common Factor (GCD/HCF) and Least Common Multiple (LCM) for two or more positive integers with prime factorization trees and Euclidean algorithm division steps.
Interactive GCF & LCM Calculator
Compute the Greatest Common Factor (GCF/GCD) and Least Common Multiple (LCM) for two or more integers with step-by-step prime factorizations and Euclidean division proofs.
Enter 2 or more whole numbers (e.g. 25, 75, 275). Results update instantly.
Prime Factor Power Matrix & Intersection
Lowest-Power Rule: ∏ pimin(e)| Integer | Canonical Prime Factorization | Expanded Factors |
|---|
Step-by-Step Mathematical Proofs
Compare analytical prime factor intersection and Euclidean recursive division.
What is the Greatest Common Factor (GCF)?
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 two or more numbers evenly without a remainder. If GCF(a, b) = 1, the numbers are coprime.
GCF & Divisor Fundamentals
In number theory, a positive integer d is a divisor (or factor) of an integer n if there exists an integer k such that n = d × k (meaning division produces zero remainder: n mod d = 0).
The Greatest Common Factor (GCF), universally written in mathematical literature as &gcd;(a, b), represents the maximal element in the intersection set of all divisors of a and b:
When two integers share no common positive factor other than 1, they are called coprime or relatively prime (e.g., 8 and 15, or any two distinct prime numbers).
The GCF operation is strictly associative and commutative, allowing any number of integers to be simplified pairwise in arbitrary order.
The Two Primary GCF Algorithms
Depending on whether you are working with small numbers by hand or large values programmatically, two core mathematical algorithms are used to determine the GCF:
The Prime Factorization Method (Lowest Power Rule)
By the Fundamental Theorem of Arithmetic, every integer greater than 1 has a unique prime factorization. To find &gcd;(a, b), express both numbers as prime products and take the minimum exponent of each common prime:
Best for: Classroom homework, small numbers under 1,000, and algebraic monomial factoring (e.g., &gcd;(12x³y, 18x²y²) = 6x²y).
The Euclidean Algorithm (Division by Remainders)
Described by the Greek mathematician Euclid in Elements (~300 BC), this algorithm relies on the principle that &gcd;(a, b) = &gcd;(b, a mod b). Repeated integer division produces successively smaller remainders until the remainder is zero:
| Step | Division Formula | Quotient (q) | Remainder (r) |
|---|---|---|---|
| 1 | 252 = 105 × 2 + 42 | 2 | 42 |
| 2 | 105 = 42 × 2 + 21 | 2 | 21 |
| 3 | 42 = 21 × 2 + 0 | 2 | 0 (→ GCF = 21) |
Best for: Large integers, cryptographic computing, and fast logarithmic convergence in $O(\log(\min(a, b)))$ steps.
GCF and LCM Dual Relationship
The Greatest Common Factor (GCF) and the Least Common Multiple (LCM) are fundamental mathematical duals. For any two positive integers a and b, the product of their GCF and LCM is strictly equal to the product of the original integers:
This identity provides the most computationally efficient method for finding the LCM: first compute &gcd;(a, b) using the Euclidean algorithm, then compute:
Real-World Applications & Industry Use Cases
Greatest Common Divisors govern optimal spatial packaging, cryptography, and engineering synchronizations:
Tile & Architectural Layouts
Finding the largest square floor tiles that will cover a rectangular room of dimensions 240 cm × 360 cm without cutting any tiles requires calculating &gcd;(240, 360) = 120 cm square tiles.
RSA Public-Key Cryptography
Digital encryption keys require selecting a public exponent e such that &gcd;(e, φ(n)) = 1 (coprimality with Euler's totient function). The Extended Euclidean Algorithm is used to derive the private decryption key.
Mechanical Gear Mesh & Wear Distribution
Engineers design interlocking gear teeth counts to be coprime (e.g. 17 teeth and 43 teeth, with GCF = 1) so that every tooth on gear A touches every tooth on gear B before repeating, ensuring uniform wear.
Inventory Packaging & Batching
Distributing 120 pens, 80 notebooks, and 60 keychains into identical promotional gift kits without leftovers requires computing &gcd;(120, 80, 60) = 20 kits.
Step-by-Step Worked Examples
Examine these verified numerical solutions across varying calculation difficulty tiers:
Find GCF(48, 72)
1. Prime factorize 48: 48 = 2⁴ × 3¹.
2. Prime factorize 72: 72 = 2³ × 3².
3. Common prime factors: 2 and 3.
4. Take lowest powers: 2³ × 3¹ = 8 × 3 = 24.
5. Final: GCF(48, 72) = 24 (LCM = 144).
Find GCF(1071, 462)
1. 1071 ÷ 462 = 2 remainder 147 → 1071 = 462 × 2 + 147
2. 462 ÷ 147 = 3 remainder 21 → 462 = 147 × 3 + 21
3. 147 ÷ 21 = 7 remainder 0 → 147 = 21 × 7 + 0
4. Last non-zero remainder: 21.
5. Final: GCF(1071, 462) = 21.
Common Calculation Pitfalls
Remember: GCF is a factor/divisor (always ≤ min(a, b)), whereas LCM is a multiple (always ≥ max(a, b)).
When using prime factorizations, always select the lowest power of common primes for GCF. Highest powers produce the LCM.
Lead Developer & Founder of Basic Math Tools. Specializes in browser-native computational algorithms and applied mathematics.
Mathematics & curriculum specialists. Audited against standard algebraic and arithmetic principles.