CalculatorFree.net

GCF Calculator — Greatest Common Factor

Enter two or more numbers separated by commas. The calculator finds the greatest common factor using the Euclidean algorithm and shows every step.

Results

GCF (48, 18):6
LCM (48, 18):144
Prime Factorization:
48 = 2^4 × 3
18 = 2 × 3^2
Euclidean Algorithm — Step-by-step:
GCF(48, 18):
  48 = 2 × 18 + 12
  18 = 1 × 12 + 6
  12 = 2 × 6 + 0
  GCF = 6
LCM from GCF:
LCM(48, 18) = |48 × 18| / GCF
LCM = 864 / 6
LCM = 144

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 them exactly, with no remainder. It is also called the greatest common divisor (GCD) or the highest common factor (HCF) — all three terms mean the same thing.

For example, the factors of 12 are 1, 2, 3, 4, 6, and 12. The factors of 18 are 1, 2, 3, 6, 9, and 18. The common factors are 1, 2, 3, and 6. The greatest of these is 6, so GCF(12, 18) = 6.

GCF is a fundamental concept in number theory and has direct practical uses in simplifying fractions, dividing quantities into equal groups, and solving problems involving repeating patterns or cycles.

Method 1: The Euclidean Algorithm

The Euclidean algorithm is the most efficient method for finding the GCF of two numbers, especially when the numbers are large. It was described by Euclid around 300 BCE in his work Elements and remains one of the oldest algorithms still in widespread use today.

The algorithm is based on the principle that the GCF of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number.

Steps for GCF(252, 105):

Step 1: Divide 252 by 105. Remainder = 252 − 2 × 105 = 42.
Step 2: Divide 105 by 42. Remainder = 105 − 2 × 42 = 21.
Step 3: Divide 42 by 21. Remainder = 0.
GCF = 21 (the last non-zero remainder).

Once you reach a remainder of 0, the divisor at that step is the GCF. The Euclidean algorithm always terminates because the remainders strictly decrease at each step.

Method 2: Prime Factorization

The prime factorization method is more intuitive and works well for smaller numbers where you can easily factor each one. To find the GCF:

  1. Write the complete prime factorization of each number.
  2. Identify every prime factor that appears in all of the numbers.
  3. For each shared prime factor, take the smallest exponent across all numbers.
  4. Multiply these selected prime powers together. The result is the GCF.

Example: GCF(360, 126)

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5
126 = 2 × 3 × 3 × 7 = 2 × 3² × 7
Common primes: 2 (min exponent: 1) and 3 (min exponent: 2)
GCF = 2¹ × 3² = 2 × 9 = 18

Using GCF to Simplify Fractions

The most common real-world use of GCF is reducing fractions to their simplest form. A fraction is in lowest terms when the numerator and denominator share no common factor other than 1 — in other words, their GCF equals 1.

To simplify a fraction, divide both the numerator and denominator by their GCF. The value of the fraction does not change because you are dividing both parts by the same number.

Example: Simplify 84/112

GCF(84, 112): 112 = 1 × 84 + 28; 84 = 3 × 28 + 0. GCF = 28.
84 ÷ 28 = 3 and 112 ÷ 28 = 4.
Simplified fraction: 3/4

GCF for Three or More Numbers

The GCF can be extended to three or more numbers. The key property is that the GCF operation is associative: GCF(A, B, C) = GCF(GCF(A, B), C).

Example: GCF(24, 36, 60)

GCF(24, 36): 36 = 1 × 24 + 12; 24 = 2 × 12 + 0. GCF = 12.
GCF(12, 60): 60 = 5 × 12 + 0. GCF = 12.
GCF(24, 36, 60) = 12

This is useful when dividing items into equal groups. For example, if you have 24 apples, 36 oranges, and 60 bananas that you want to divide into identical bags with no leftovers, the maximum number of bags is GCF(24, 36, 60) = 12, with 2 apples, 3 oranges, and 5 bananas per bag.

Frequently Asked Questions

What is the greatest common factor (GCF)?

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 evenly into both 12 and 18. GCF is used to simplify fractions to their lowest terms and to solve many number theory problems.

What is the Euclidean algorithm for finding GCF?

The Euclidean algorithm finds the GCF by repeatedly applying the division algorithm. Given two numbers A and B (where A > B): divide A by B and find the remainder R. Then replace A with B and B with R. Repeat until the remainder is 0. The last non-zero remainder is the GCF. Example: GCF(48, 18). Step 1: 48 = 2 × 18 + 12. Step 2: 18 = 1 × 12 + 6. Step 3: 12 = 2 × 6 + 0. GCF = 6.

How do you find the GCF using prime factorization?

To find GCF by prime factorization: (1) write the prime factorization of each number, (2) identify all prime factors that appear in every number, (3) for each shared prime, take the lowest exponent, (4) multiply these together. Example: GCF(36, 48). 36 = 2² × 3². 48 = 2⁴ × 3. Common primes: 2 (min exponent 2) and 3 (min exponent 1). GCF = 2² × 3 = 4 × 3 = 12.

How is GCF used to simplify fractions?

To simplify a fraction to lowest terms, divide both the numerator and denominator by their GCF. For example, to simplify 36/48: GCF(36, 48) = 12. Divide both by 12: 36 ÷ 12 = 3 and 48 ÷ 12 = 4. The simplified fraction is 3/4. This works because dividing top and bottom by the same number does not change the value of the fraction — it only removes common factors.

What is the relationship between GCF and LCM?

The GCF and LCM of two numbers A and B are related by the formula: GCF(A, B) × LCM(A, B) = A × B. This means that once you know the GCF, you can find the LCM quickly: LCM(A, B) = (A × B) / GCF(A, B). For example: A = 12, B = 18. GCF = 6. LCM = (12 × 18) / 6 = 216 / 6 = 36. This relationship is useful for working with fractions and scheduling problems.

Related Calculators