Greatest Common Factor Calculator
Find the GCF (GCD) of two or more numbers using prime factorization and Euclidean algorithm. Enter values for instant results with step-by-step formulas.
Reviewed by Manoj Kumar, Mathematics Educator
Formula
GCF(a, b) via Euclidean: a = b x q + r, repeat until r = 0
The Euclidean algorithm repeatedly divides the larger number by the smaller, replacing the larger with the remainder, until the remainder is zero. The last non-zero remainder is the GCF. Alternatively, GCF equals the product of common prime factors raised to their minimum powers. LCM(a,b) = (a x b) / GCF(a,b).
Worked Examples
Example 1: GCF of 48 and 36 Using Euclidean Algorithm
Problem:Find the GCF of 48 and 36, and use it to simplify the fraction 48/36.
Solution:Euclidean Algorithm:\n48 = 36 x 1 + 12\n36 = 12 x 3 + 0\nGCF = 12\n\nPrime Factorization:\n48 = 2^4 x 3\n36 = 2^2 x 3^2\nCommon: 2^2 x 3 = 12\n\nSimplify 48/36: divide both by 12 = 4/3\nLCM = (48 x 36) / 12 = 144
Result:GCF(48, 36) = 12 | LCM = 144 | 48/36 simplifies to 4/3
Example 2: GCF of 105 and 252
Problem:Find the GCF of 105 and 252 using the Euclidean algorithm and list all common factors.
Solution:252 = 105 x 2 + 42\n105 = 42 x 2 + 21\n42 = 21 x 2 + 0\nGCF = 21\n\n105 = 3 x 5 x 7\n252 = 2^2 x 3^2 x 7\nCommon factors: 1, 3, 7, 21\nLCM = (105 x 252) / 21 = 1260
Result:GCF(105, 252) = 21 | Common factors: 1, 3, 7, 21 | LCM = 1260
Frequently Asked Questions
What is the Greatest Common Factor and how is it defined?
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. For example, the GCF of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly. The GCF is always at least 1, since 1 divides every integer. Two numbers whose GCF is 1 are called coprime or relatively prime. The GCF is a fundamental concept in number theory and has practical applications in simplifying fractions, solving Diophantine equations, and in cryptographic algorithms like RSA encryption.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy