Greatest Common Factor Calculator
Find the greatest common factor of two integers in seconds. Use it to simplify fractions, factor expressions, or solve number-theory problems.
About this calculator
The Greatest Common Factor (GCF), also called the Greatest Common Divisor (GCD), is the largest integer that divides both numbers without leaving a remainder. This calculator uses the Euclidean algorithm: repeatedly replace the larger number with the remainder of dividing the two numbers until the remainder is zero — the last non-zero value is the GCF. In symbols: GCF(a, b) = GCF(b, a mod b), with base case GCF(a, 0) = a. The algorithm is efficient even for very large numbers. GCF is essential for reducing fractions to lowest terms (divide numerator and denominator by their GCF), finding common denominators, and solving Diophantine equations. Negative inputs are handled by taking absolute values first.
How to use
Find the GCF of 48 and 18. Enter First Number = 48 and Second Number = 18. The Euclidean algorithm proceeds: 48 mod 18 = 12 → 18 mod 12 = 6 → 12 mod 6 = 0. The last non-zero remainder is 6, so GCF(48, 18) = 6. To verify: 48 ÷ 6 = 8 and 18 ÷ 6 = 3, both whole numbers, and no larger integer divides both evenly. The fraction 18/48 simplifies to 3/8.
Frequently asked questions
What is the difference between GCF and LCM and when should I use each?
The GCF (Greatest Common Factor) is the largest number that divides both integers evenly, while the LCM (Least Common Multiple) is the smallest number that both integers divide into evenly. Use the GCF when simplifying fractions or factoring expressions. Use the LCM when adding or subtracting fractions with different denominators. The two are related by the formula: GCF(a, b) × LCM(a, b) = a × b, so knowing one lets you quickly find the other.
How do I use the GCF to simplify a fraction?
To reduce a fraction to its simplest form, divide both the numerator and denominator by their GCF. For example, to simplify 36/60, first find GCF(36, 60) = 12. Then divide: 36 ÷ 12 = 3 and 60 ÷ 12 = 5, giving 3/5. A fraction is in its lowest terms when the GCF of the numerator and denominator is 1 — these numbers are called coprime or relatively prime. This process is fundamental in arithmetic, algebra, and working with ratios.
Why does the Euclidean algorithm work for finding the GCF?
The Euclidean algorithm is based on the principle that GCF(a, b) = GCF(b, a mod b). This works because any common divisor of a and b also divides a − b, and therefore divides a mod b (which is just repeated subtraction). By repeatedly reducing the problem to smaller numbers, the algorithm eventually reaches zero, at which point the remaining non-zero value is the GCF. Euclid described this method around 300 BCE, making it one of the oldest algorithms still in widespread use today.