GCF of Two Numbers
Enter two positive integers to find their Greatest Common Factor using prime factorization and the Euclidean algorithm.
GCF of Multiple Numbers
Enter three or more integers separated by commas to find the Greatest Common Factor of the entire set.
GCF and LCM Calculator
Find both the Greatest Common Factor and the Least Common Multiple of two numbers at once, with their relationship verified.
Fraction Simplifier Using GCF
Enter the numerator and denominator of a fraction to reduce it to its simplest form using the Greatest Common Factor.
What is the Greatest Common Factor?
The Greatest Common Factor (GCF) of two or more integers is the largest positive integer that divides each of the given integers without leaving a remainder. It is also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF).
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18
Common factors: 1, 2, 3, 6
Greatest Common Factor: 6
How to Find the GCF Using Prime Factorization
The prime factorization method breaks each number into its prime factors. The GCF is found by multiplying together only the prime factors that are shared by all numbers, using the lowest power that appears in any factorization.
Step 2: Identify prime factors common to all numbers.
Step 3: For each shared prime, take the lowest power.
Step 4: Multiply these together to get the GCF.
Example: GCF(36, 48)
36 = 2^2 x 3^2
48 = 2^4 x 3^1
Shared primes: 2 (min power 2) and 3 (min power 1)
GCF = 2^2 x 3^1 = 4 x 3 = 12
How to Find the GCF Using the Euclidean Algorithm
The Euclidean algorithm is a fast method that uses repeated division. It works by replacing the larger number with the remainder when the larger is divided by the smaller, until the remainder is zero.
48 = 18 x 2 + 12
18 = 12 x 1 + 6
12 = 6 x 2 + 0
GCF = 6
GCF and Simplifying Fractions
The GCF is directly used to simplify fractions to their lowest terms. Dividing both the numerator and denominator by their GCF reduces the fraction to its simplest form.
GCF(36, 48) = 12
36 / 12 = 3
48 / 12 = 4
Simplified fraction: 3/4
GCF vs LCM
The GCF and LCM are complementary concepts. The GCF is the largest number that divides both integers evenly, while the LCM is the smallest number that both integers divide into evenly. For any two positive integers a and b:
This means: LCM(a, b) = (a x b) / GCF(a, b)