GCF Calculator — Greatest Common Factor with Euclidean Algorithm &

How Greatest Common Factor Works

GCF(a, b) = largest number dividing both a and b evenly

The Greatest Common Factor (GCF), also called the Greatest Common Divisor (GCD), is the largest positive integer that divides both numbers without a remainder. This calculator demonstrates two methods: the Euclidean algorithm (by repeated division) and prime factorization (by comparing shared prime factors with a visual Venn diagram).

a, b

Input Numbers — The positive integers to find the GCF of. Both must be whole numbers greater than 0.

GCF

Greatest Common Factor — The largest positive integer that divides both a and b without a remainder.

Euclidean Algorithm

Algorithm Steps — A step-by-step division process that efficiently finds the GCF without factoring.

How to Use

1. Enter two positive integers to find their Greatest Common Factor.
2. View the GCF result along with the step-by-step Euclidean algorithm showing each division.
3. The Venn diagram visualizes the prime factors of each number, with shared factors in the overlapping region.
4. The shared prime factors section lists the primes common to both numbers, which multiply to form the GCF.

Quick Reference

Understanding the Result

The Greatest Common Factor (GCF) is the largest number that divides into both input numbers evenly. It is also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF). The Euclidean algorithm is the most efficient method for finding the GCF, especially for large numbers: it works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder reaches zero. The last non-zero remainder is the GCF. This algorithm has been known since ancient Greece (circa 300 BCE) and remains one of the oldest numerical algorithms still in common use. The alternative method, prime factorization, breaks each number into its prime building blocks; the GCF is the product of shared prime factors raised to the lowest exponent appearing in either factorization. For example, 24 = 2 × 2 × 2 × 3 and 36 = 2 × 2 × 3 × 3, so the shared primes are 2 (twice) and 3 (once), giving GCF = 2 × 2 × 3 = 12.

Worked Examples

Frequently Asked Questions

What is the Euclidean algorithm?

The Euclidean algorithm finds GCF/GCD by repeated division. Example for GCF(24, 36): divide 36 by 24 to get remainder 12, then divide 24 by 12 to get remainder 0. The last non-zero remainder (12) is the GCF. The calculator shows each step of this process. This method is much faster than factoring for large numbers.

How does the Venn diagram help find GCF?

The Venn diagram shows the prime factors of each number in overlapping circles. The shared factors (in the intersection) multiply together to give the GCF. For example, 24 = 2 × 2 × 2 × 3 and 36 = 2 × 2 × 3 × 3. The shared factors are two 2s and one 3, so GCF = 2 × 2 × 3 = 12. The visual layout makes the concept intuitive.

What is the practical use of GCF?

GCF is used for simplifying fractions (divide numerator and denominator by the GCF to get lowest terms), dividing items into the largest possible equal groups, solving ratio problems, and in modular arithmetic and cryptography. In construction, GCF helps determine the largest common measurement for cutting materials.

What does it mean when GCF equals 1?

When GCF(a, b) = 1, the two numbers are called co-prime or relatively prime — they share no common prime factors. For example, 14 and 15 are co-prime. This has important implications: the fraction a/b is already in its simplest form, and the Chinese Remainder Theorem guarantees unique solutions modulo a×b in modular arithmetic.

How is GCF related to LCM?

The fundamental relationship is: LCM(a, b) × GCF(a, b) = a × b. This means you can find either one from the other. For example, for a=24, b=36, GCF=12, so LCM = (24×36)/12 = 864/12 = 72. This formula is why you only need to compute one of them — the other follows immediately.

Can the Euclidean algorithm handle very large numbers?

Yes — the Euclidean algorithm runs in O(log min(a,b)) time, meaning it takes only a few dozen steps even for numbers with hundreds of digits. For example, finding the GCF of two 100-digit numbers takes fewer than 700 iterations. This makes it one of the most efficient algorithms in all of computer science and a cornerstone of modern cryptography.

Pro Tips

• →For two numbers where one is a multiple of the other, the GCF is the smaller number. For example, GCF(12, 36) = 12. No calculation needed.
• →The Euclidean algorithm is lightning-fast even for numbers with hundreds of digits. In fact, its efficiency is why it underpins the RSA encryption algorithm.
• →If both numbers are even, the GCF is at least 2. Divide both by 2 repeatedly until at least one is odd — this shortcut dramatically reduces the numbers before running the full algorithm.
• →When simplifying a fraction by hand, the factor list approach (listing all common factors and picking the largest) works well for small numbers, but for large numbers, use the Euclidean algorithm or the GCF calculator.

Limitations to Know

• •This calculator finds the GCF of exactly two numbers. For three or more numbers, find the GCF of the first two, then find the GCF of that result with the third, and so on: GCF(a, b, c) = GCF(GCF(a, b), c).
• •Only positive integers are supported. Negative numbers, zero, and non-integers are rejected because GCF is defined only for positive integers in standard arithmetic.
• •The prime factorization method used in the Venn diagram becomes computationally expensive for numbers with large prime factors (e.g., numbers near 10⁹ or larger). The Euclidean algorithm result remains accurate in those cases.

Sources

• Wikipedia - Greatest Common Divisor
• Wolfram MathWorld - Greatest Common Divisor