GCF and LCM Calculator
Find the Greatest Common Factor and Least Common Multiple of any two positive integers, with full prime factorization and step-by-step working.
This calculator finds the Greatest Common Factor (GCF) and Least Common Multiple (LCM) of any two positive integers. Enter both numbers and get both answers instantly, along with prime factorization and the Euclidean algorithm steps so you can see how the answer was reached. Use it for simplifying fractions, finding common denominators, scheduling problems, or any time you need to know what two numbers share or how they combine.
How this tool works
Enter two positive whole numbers. The tool runs the Euclidean algorithm to find the GCF: it repeatedly divides the larger number by the smaller, takes the remainder, and repeats until the remainder is zero. The last non-zero remainder is the GCF. The LCM is then found using the relationship LCM(a, b) = (a × b) ÷ GCF(a, b). Toggle Show steps to see the full prime factorization and each division step.
Worked examples
Simplifying a fraction
You want to reduce 48/36 to lowest terms. GCF(48, 36) = 12. Divide both by 12: 48/12 = 4 and 36/12 = 3. The simplified fraction is 4/3.
Finding a common denominator
To add 1/12 and 1/18, you need a common denominator. LCM(12, 18) = 36. Convert: 1/12 = 3/36 and 1/18 = 2/36. Add them: 3/36 + 2/36 = 5/36.
Scheduling problem
Two buses leave a stop every 8 and 12 minutes. LCM(8, 12) = 24. They will next depart together in 24 minutes.
Frequently asked questions
What is the Greatest Common Factor (GCF)?
The Greatest Common Factor, also called the Greatest Common Divisor (GCD), is the largest positive integer that divides both numbers without leaving a remainder. For 12 and 18, the GCF is 6 because 6 is the largest number that goes into both 12 and 18 evenly.
What is the Least Common Multiple (LCM)?
The Least Common Multiple is the smallest positive integer that is divisible by both numbers. For 4 and 6, the LCM is 12 because 12 is the smallest number that both 4 and 6 divide into evenly. The LCM is used when finding a common denominator for fractions.
What is the Euclidean algorithm?
The Euclidean algorithm is an efficient method for computing the GCF. It works by repeatedly replacing the larger number with the remainder when the larger is divided by the smaller. When the remainder reaches zero, the last non-zero number is the GCF. For GCF(48, 18): 48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0. The GCF is 6.
How do GCF and LCM relate to each other?
For any two positive integers a and b, GCF(a, b) × LCM(a, b) = a × b. This means once you know the GCF, you can always find the LCM with LCM = (a × b) ÷ GCF. For 12 and 18: GCF = 6, so LCM = (12 × 18) ÷ 6 = 216 ÷ 6 = 36.
What does it mean when the GCF equals 1?
When GCF(a, b) = 1, the two numbers are called coprime or relatively prime. They share no common factors other than 1. For example, 8 and 15 are coprime: GCF(8, 15) = 1. Coprime numbers have an LCM equal to their product: LCM(8, 15) = 120.
How is GCF used to simplify fractions?
To simplify a fraction, divide both the numerator and denominator by their GCF. For 24/36, the GCF is 12. Divide both: 24÷12 = 2 and 36÷12 = 3. The simplified fraction is 2/3. Dividing by the GCF gives the fraction in lowest terms in one step.
What is prime factorization and how does it find the GCF?
Prime factorization breaks a number into its prime factors. For GCF, find the prime factorization of both numbers and take the lowest power of each shared prime. For 36 = 2² × 3² and 48 = 2⁴ × 3, the shared primes are 2 and 3. Take 2¹ and 3¹, giving GCF = 2 × 3 = 6. Wait — the lower exponent of 2 is min(2,4) = 2 and min(2,1) = 1 for 3. GCF = 2² × 3 = 12.
Can these methods be extended to more than two numbers?
Yes. To find the GCF of three or more numbers, compute GCF(a, b) first, then compute GCF(result, c), and so on. The same chain approach works for LCM. For example, GCF(12, 18, 24) = GCF(GCF(12, 18), 24) = GCF(6, 24) = 6.