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 for accuracy by Manoj Kumar, Mathematics Educator
Greatest Common Factor Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: GCF(a, b) via Euclidean: a = b x q + r, repeat until r = 0
Worked example — GCF(48, 36) = 12 | LCM = 144 | 48/36 simplifies to 4/3
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: 48 = 36 x 1 + 12 36 = 12 x 3 + 0 GCF = 12 Prime Factorization: 48 = 2^4 x 3 36 = 2^2 x 3^2 Common: 2^2 x 3 = 12 Simplify 48/36: divide both by 12 = 4/3 LCM = (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 105 = 42 x 2 + 21 42 = 21 x 2 + 0 GCF = 21 105 = 3 x 5 x 7 252 = 2^2 x 3^2 x 7 Common factors: 1, 3, 7, 21 LCM = (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.
How does the Euclidean algorithm find the GCF?
The Euclidean algorithm is one of the oldest known algorithms, dating back to about 300 BCE. It works by repeatedly dividing the larger number by the smaller number and replacing the larger number with the remainder. The process continues until the remainder is zero, at which point the last non-zero remainder is the GCF. For example, to find GCF(48, 36): 48 divided by 36 gives remainder 12, then 36 divided by 12 gives remainder 0, so GCF is 12. The algorithm is remarkably efficient, requiring at most 5 times the number of digits of the smaller number in divisions. This efficiency makes it practical even for very large numbers used in modern cryptography.
How do you find the GCF using prime factorization?
To find the GCF using prime factorization, first break each number into its prime factors. Then identify the prime factors that appear in both factorizations and take the lowest power of each common prime. Multiply these together to get the GCF. For example, for 48 and 36: 48 = 2^4 times 3, and 36 = 2^2 times 3^2. The common primes are 2 and 3. Taking the minimum powers gives 2^2 times 3^1 = 4 times 3 = 12, so GCF(48, 36) = 12. While this method is intuitive and educational, the Euclidean algorithm is more efficient for large numbers because prime factorization becomes computationally expensive as numbers grow.
What is the relationship between GCF and LCM?
The GCF and LCM (Least Common Multiple) of two numbers are related by a simple but powerful formula: GCF(a, b) times LCM(a, b) equals a times b. This means you can find the LCM once you know the GCF by computing LCM = (a times b) divided by GCF(a, b). For example, GCF(12, 18) = 6, so LCM(12, 18) = (12 times 18) / 6 = 36. This relationship holds because the GCF captures the shared prime factors while the LCM captures the union of prime factors. In prime factorization terms, the GCF uses the minimum exponent of each prime while the LCM uses the maximum exponent of each prime.
How is the GCF used to simplify fractions?
To simplify a fraction to its lowest terms, divide both the numerator and denominator by their GCF. For example, to simplify 48/36, first find GCF(48, 36) = 12, then divide both parts by 12 to get 4/3. This produces the simplest equivalent fraction because no integer greater than 1 divides both the new numerator and denominator. A fraction is in lowest terms when the GCF of its numerator and denominator is 1. This process is fundamental in algebra, arithmetic, and anywhere fractions are used. Without GCF simplification, operations with fractions would produce increasingly large and unwieldy numbers that obscure the true proportional relationships.
What does it mean when two numbers are coprime?
Two numbers are coprime (also called relatively prime or mutually prime) when their GCF is 1, meaning they share no common factor other than 1. For example, 8 and 15 are coprime because the factors of 8 are 1, 2, 4, 8 and the factors of 15 are 1, 3, 5, 15, with only 1 in common. Coprimality does not require either number to be prime itself. Coprime numbers are important in number theory, particularly in modular arithmetic and cryptography. The RSA encryption algorithm depends on choosing two large coprime numbers. The Euler totient function counts how many numbers less than n are coprime to n, which is central to many encryption schemes.
Can you find the GCF of more than two numbers?
Yes, you can find the GCF of three or more numbers by applying the GCF operation iteratively. First compute GCF(a, b), then compute GCF of that result with c, and continue with additional numbers. For example, GCF(12, 18, 24) is computed as GCF(GCF(12, 18), 24) = GCF(6, 24) = 6. The order does not matter because the GCF operation is both commutative and associative. Alternatively, using prime factorization, find the common primes across all numbers and take the minimum exponent of each. For 12 = 2^2 times 3, 18 = 2 times 3^2, 24 = 2^3 times 3: common primes are 2 and 3 with minimum exponents 1 and 1, giving GCF = 2 times 3 = 6.
How is the GCF used in solving Diophantine equations?
Diophantine equations are polynomial equations where only integer solutions are sought, named after the ancient Greek mathematician Diophantus. The linear Diophantine equation ax + by = c has integer solutions if and only if GCF(a, b) divides c. The extended Euclidean algorithm not only finds GCF(a, b) but also finds integers x and y such that ax + by = GCF(a, b), providing a particular solution from which all solutions can be derived. For example, 48x + 36y = 12 has solutions because GCF(48, 36) = 12 divides 12. The extended algorithm gives x = 1, y = -1 as one solution, and the general solution is x = 1 + 3t, y = -1 - 4t for any integer t. This technique is used in cryptography and computer science.
What is the Extended Euclidean Algorithm?
The Extended Euclidean Algorithm is an extension of the standard Euclidean algorithm that, in addition to computing the GCF of two numbers a and b, also finds integers x and y satisfying the equation ax + by = GCF(a, b). This is known as Bezout identity. The algorithm works by tracking the coefficients through each step of the division process, working backwards from the last non-zero remainder. These coefficients are essential for finding modular multiplicative inverses, which are used extensively in RSA and other public-key cryptosystems. For example, to find the modular inverse of 7 mod 11, we solve 7x + 11y = 1, yielding x = 8, meaning 7 times 8 = 56 which is 1 mod 11.
Why is the GCF important in real-world applications?
The GCF has numerous practical applications beyond pure mathematics. In manufacturing, it helps determine the largest tile size that evenly covers a rectangular floor without cutting. In music theory, the GCF of two frequencies determines the fundamental frequency of their combined sound. In scheduling, the GCF of two cycle lengths determines how often two periodic events coincide. In computing, the binary GCD algorithm is used in rational arithmetic libraries to keep fractions in lowest terms, preventing integer overflow. In cryptography, the GCF is central to RSA key generation and to Pollard factorization algorithms. Even in everyday cooking, finding the GCF of ingredient quantities helps scale recipes to different serving sizes.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮GCF Calculator - Greatest Common Factor
Calculate gcfcalculator greatest common factor with inputs, formulas, and instant results.
🧮LCM Calculator - Least Common Multiple
Calculate lcmcalculator least common multiple with inputs, formulas, and instant results.
🧮LCD Calculator - Least Common Denominator
Calculate lcdcalculator least common denominator with inputs, formulas, and instant results.
🧮Least Common Multiple Calculator
Find the LCM of two or more numbers using prime factorization and the GCF method.
🧮Annulus Area Calculator
Calculate annulus area with inputs, formulas, and instant results.
🧮Area Calculator
Calculate area with inputs, formulas, and instant results.
🧮Area of a Rectangle Calculator
Calculate the area, perimeter, and diagonal of a rectangle. Find missing sides from known area. Convert between metric and imperial area units.
🧮Area of Crescent Calculator
Calculate area of crescent with inputs, formulas, and instant results.