Skip to content
TheCalcUniverse

Greatest Common Factor

Find the Greatest Common Factor (also called GCD or HCF) of two numbers using both the Euclidean algorithm with step-by-step division and prime factorization.

✓ Tested formula & cited sources Checked against independent sources · Oct 14, 2026 Private: runs in your browser

Enter the first positive whole number (up to 9,007,199,254,740,991)

Enter the second positive whole number (up to 9,007,199,254,740,991)

Results

GCF of 24 and 36

12

Euclidean Algorithm
36 = 24 × 1 + 12 | 24 = 12 × 2 + 0 | GCF(24, 36) = 12
Shared Prime Factors
2^2 × 3

The formula

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

a, b
Input Numbers
GCF
Greatest Common Factor
Euclidean Algorithm
Algorithm Steps

Worked example — Number A 24, Number B 36

GCF of 24 and 36 = 12

Full explanation ↓

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.
The GCF is the product of shared prime factors raised to the lowest exponent in either factorization.

Worked Examples

Simplify the fraction 42/56 to its lowest terms using GCF.

a = 42 · b = 56

GCF(42, 56) = 14

Divide both numerator and denominator by 14: 42÷14=3, 56÷14=4. The simplified fraction is 3/4. The Euclidean algorithm: 56 = 42×1 + 14, 42 = 14×3 + 0.

A baker has 48 chocolate chip cookies and 72 oatmeal cookies. What is the largest equal group size for gift boxes?

a = 48 · b = 72

GCF(48, 72) = 24

Each gift box can hold 24 cookies, using 2 boxes for chocolate chip (48/24=2) and 3 boxes for oatmeal (72/24=3). This uses all cookies with no leftovers.

Check if 14 and 15 are co-prime (relatively prime) for use in modular arithmetic.

a = 14 · b = 15

GCF(14, 15) = 1

Since the GCF is 1, the numbers are co-prime. This means they share no common prime factors and their product 14×15=210 equals their LCM. Co-prime numbers are essential in cryptography and modular arithmetic.

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.

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

GCF via prime factorsProduct of shared primes (lowest exponent)
GCF via EuclideanGCD(a,b) = GCD(b, a mod b) until remainder 0
LCM relationshipLCM(a,b) × GCF(a,b) = a × b
Co-prime (relatively prime)GCF = 1 (e.g. 14 and 15)
Common divisorAny factor shared by both numbers
GCF of same numberGCF(a, a) = a

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 whole numbers up to 9,007,199,254,740,991 (2⁵³ − 1) are supported; beyond that a JavaScript number is no longer exact. Zero, negatives and decimals give no result (by convention GCF(0, n) = n and GCF(−a, b) = GCF(a, b), but both are outside this tool).
  • •The prime-factor Venn diagram uses Miller–Rabin and Pollard rho, so it stays instant even for two 15-digit primes; the Euclidean steps are exact for every supported input.

Sources

Was this calculator helpful?
Cite this calculator

TheCalcUniverse. "GCF Calculator — Greatest Common Factor (Euclid)." TheCalcUniverse, 2026, https://thecalcuniverse.com/math/gcf-calculator/. Accessed October 25, 2026.

Embed this calculator on your site

Free to embed. Paste this into any HTML page — it stays up to date automatically.

Open embed ↗

You may also like