What Is the Greatest Common Factor?
A teacher has 24 pencils and 36 erasers to distribute evenly among students. What is the maximum number of identical gift bags she can make with no leftovers? The answer is 12, because 12 is the largest number that divides both 24 and 36 without a remainder. That number 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 positive integer that divides two or more numbers without leaving a remainder. The concept has been studied for over 2,000 years. The Encyclopedia of Mathematicstraces the algorithm back to Euclid's Elements, written around 300 BC, making it one of the oldest algorithms still in regular use.
GCF is a foundational concept in arithmetic and algebra. It is used to simplify fractions, solve ratio problems, factor algebraic expressions, and design efficient computational algorithms. This calculator also computes the least common multiple (LCM), which is the smallest number that both values divide into evenly. For finding all factors of a single number, use our Factor Calculator.
What This Calculator Does
Enter two or more integers and this calculator finds both the GCF and LCM instantly. It accepts comma-separated or space-separated values and handles any number of inputs.
- Inputs: Two or more non-zero integers
- Outputs: Greatest common factor (GCF) and least common multiple (LCM)
How the Calculation Works
Euclidean Algorithm for GCF
GCF(a, b) = GCF(b, a mod b), repeated until b = 0
The Euclidean algorithm is the most efficient way to compute the GCF. It repeatedly replaces the larger number with the remainder of dividing the two numbers until the remainder is zero. The last non-zero remainder is the GCF. According to Wolfram MathWorld, Gabriel Lame proved in 1844 that the algorithm never requires more steps than five times the number of digits in the smaller number, making it remarkably efficient even for very large inputs.
For more than two numbers, the GCF is computed step by step: GCF(a, b, c) = GCF(GCF(a, b), c).
LCM Formula
LCM(a, b) = |a x b| / GCF(a, b)
The LCM is derived from the GCF using this relationship. Multiplying two numbers and dividing by their GCF gives the smallest number that both divide into evenly. For a dedicated LCM tool, try our LCM Calculator.
How to Use the Calculator
- Type two or more integers into the input field, separated by commas or spaces
- The GCF and LCM update instantly as you type
- All numbers must be non-zero integers
Example Calculations
Example 1: Maria, a 7th grade math teacher in Houston, needs to simplify the fraction 84/126 for her students. She enters 84 and 126 into the calculator. The Euclidean algorithm runs: 126 mod 84 = 42, then 84 mod 42 = 0. The GCF is 42. Dividing both by 42 gives 2/3. The LCM is (84 x 126) / 42 = 252.
Example 2: David, a computer science student in Ann Arbor, is working on a scheduling algorithm. Three processes repeat every 12, 18, and 24 seconds. He enters all three numbers. GCF(12, 18) = 6, then GCF(6, 24) = 6. The GCF is 6. LCM(12, 18) = 36, then LCM(36, 24) = 72. All three processes synchronize every 72 seconds. For fraction operations that use GCF in simplification, try our Fraction Calculator.
Real World Scenarios
Simplifying Fractions
A carpenter in Portland is cutting a board into equal sections. The board is 48 inches long and she needs pieces that are either 6 or 8 inches. The GCF of 48 and 8 is 8, so she can cut six 8-inch pieces with no waste. If she needs pieces of both 6 and 8 inches, the GCF of 6 and 8 is 2, meaning the largest piece size that divides both evenly is 2 inches. The GCF determines the largest unit that works for all measurements.
Scheduling and Timing
Two buses depart from a station every 12 and 18 minutes. The LCM of 12 and 18 is 36, so the buses depart together every 36 minutes. A third bus runs every 24 minutes. The LCM of all three is 72 minutes. Transit planners use LCM to synchronize schedules and minimize wait times at transfer points.
Cryptography and Computer Science
The Euclidean algorithm is not just for classroom math. It is a building block of modern cryptography. The extended Euclidean algorithm, which finds integers x and y such that ax + by = GCF(a, b), is used in RSA encryption to compute modular inverses. Every secure web transaction today relies on mathematical operations that descend directly from Euclid's 2,200-year-old algorithm.
Common Mistakes to Avoid
- Confusing GCF with LCM: The GCF is always less than or equal to the smaller number, while the LCM is always greater than or equal to the larger number. GCF(12, 18) = 6 (smaller), LCM(12, 18) = 36 (larger).
- Using 0 as an input: The GCF with zero is undefined in most practical applications. All inputs must be non-zero integers. GCF(0, 5) is technically 5 in pure mathematics, but this calculator requires non-zero inputs.
- Using decimals: GCF and LCM apply to integers only. Convert decimals to fractions before finding the GCF. For example, to find the GCF of 0.6 and 0.8, convert to 6/10 and 8/10, then find GCF(6, 8) = 2.
- Assuming GCF must be small: For two prime numbers like 7 and 11, the GCF is 1 since they share no common factors. Numbers with a GCF of 1 are called coprime or relatively prime. But for 48 and 36, the GCF is 12, which is quite large relative to the inputs.
Limitations of This Calculator
This calculator works with positive and negative integers but requires all inputs to be non-zero. It does not accept decimal numbers, fractions, or algebraic expressions. For finding the GCF of polynomials, a specialized algebra tool is needed. The calculator does not show the intermediate steps of the Euclidean algorithm. For prime factorization of a single number, use the Factor Calculator. For computing least common multiples with more options, try the LCM Calculator. Very large inputs (above 15 digits) may produce results that exceed JavaScript's safe integer limit of 9,007,199,254,740,991.
Authoritative Research and Resources
- Encyclopedia of Mathematics: Euclidean Algorithm provides a rigorous mathematical definition and historical context for the algorithm, tracing it back to Euclid's Elements (c. 300 BC) and documenting its generalizations to polynomials and Euclidean rings.
- Wolfram MathWorld: Euclidean Algorithm offers a detailed technical reference including Lame's theorem on computational complexity, the connection to continued fractions, and the algorithm's role in modern number theory and cryptography.
- NIST Unit Conversion Resources provides official US government reference materials on measurement standards and mathematical conventions, including the SI system used in scientific computing applications that rely on integer arithmetic.