AJ Designer

Greatest Common Factor Calculator

Greatest common factor of a and b

Solution

—
Share:

Greatest Common Factor

The GCF (also called GCD) is the largest integer that divides both numbers evenly. This calculator uses Euclid's algorithm to find it efficiently.

GCF via Euclid's Algorithm

How It Works

The Greatest Common Factor (GCF), also called GCD, is the largest integer that divides both numbers evenly. This calculator uses Euclid's algorithm: repeatedly divide the larger number by the smaller and take the remainder until the remainder is zero. The last non-zero remainder is the GCF. This method is much faster than listing every factor when the numbers are large.

Example Problem

Find GCF(24, 36):

  1. Start with the larger number: 36 = 1 × 24 + 12.
  2. Replace the original pair with 24 and 12.
  3. Divide again: 24 = 2 × 12 + 0.
  4. Stop when the remainder becomes 0.
  5. The last non-zero remainder is 12.
  6. Therefore, GCF(24, 36) = 12.

Key Concepts

The Greatest Common Factor (GCF), also called the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without a remainder. Euclid's algorithm finds it efficiently by repeatedly applying the division algorithm: divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero. The GCF connects to the LCM through the identity LCM(a,b) = |a*b| / GCF(a,b).

Applications

  • Fraction simplification: dividing numerator and denominator by their GCF reduces a fraction to lowest terms
  • Tiling and design: finding the largest square tile that evenly covers a rectangular floor
  • Music theory: finding the GCF of beat subdivisions to determine the simplest time signature
  • Cryptography: Euclid's algorithm is used in RSA key generation to verify that numbers are coprime

Common Mistakes

  • Confusing GCF with LCM — GCF is the largest shared factor, LCM is the smallest shared multiple; they are inverses in a sense
  • Stopping Euclid's algorithm too early — continue until the remainder is exactly zero, not just small
  • Forgetting that GCF(0, n) = n — zero is divisible by every integer, so the GCF with zero is the other number

Frequently Asked Questions

How do you find the GCF step by step?

A fast method is Euclid's algorithm: divide the larger number by the smaller, replace the pair with the smaller number and the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCF.

What is the GCF of two numbers?

The GCF is the largest number that divides both values without a remainder. For 18 and 24, the GCF is 6 because 6 is the biggest number that goes into both evenly.

How is GCF used to simplify fractions?

Divide both the numerator and denominator by their GCF. For 8/12, the GCF of 8 and 12 is 4, so 8/12 simplifies to 2/3.

What is the difference between GCF and LCM?

GCF is the largest shared factor; LCM is the smallest shared multiple. They are related by the formula LCM(a, b) = |a × b| / GCF(a, b). For 12 and 18, GCF = 6 and LCM = 36.

What is Euclid's algorithm?

Euclid's algorithm is a repeated-division method for finding the greatest common divisor. It works because GCF(a, b) = GCF(b, a mod b), so each step keeps the same answer while making the numbers smaller.

Can the GCF ever be 1?

Yes. When two numbers share no factor greater than 1, they are called coprime or relatively prime, and their GCF is 1.

Why is GCF useful outside of fractions?

GCF is useful for grouping, tiling, ratio reduction, modular arithmetic, and algorithm design. It also appears in cryptography and computer science.

Reference: Euclid's algorithm for the greatest common divisor, a standard number-theory method used in arithmetic and computer science.

GCF Formula and Method

The greatest common factor is the largest positive integer that divides both numbers evenly.

GCF(a, b) = GCF(b, a mod b)

This recursive rule is the heart of Euclid's algorithm and is one of the fastest ways to compute a GCF.

Worked Examples

Shared Factors

Find GCF(24, 36)

  • 36 = 1 × 24 + 12
  • 24 = 2 × 12 + 0
  • The last non-zero remainder is 12

Result: 12

Coprime Numbers

Find GCF(14, 25)

  • 25 = 1 × 14 + 11
  • 14 = 1 × 11 + 3
  • 11 = 3 × 3 + 2, then 3 = 1 × 2 + 1
  • The final GCF is 1

Result: 1

Larger Numbers

Find GCF(84, 126)

  • 126 = 1 × 84 + 42
  • 84 = 2 × 42 + 0
  • The last non-zero remainder is 42

Result: 42

Related Calculators

Related Sites