Math · Live
Greatest Common Factor,
with Euclid's steps.
Find the GCF (GCD) of two or more positive integers. Enter a comma-separated list and instantly see the result, the step-by-step Euclidean algorithm, the prime factorisation of every input, all common factors, and the related LCM.
Inputs
Enter integers
- Numbers
- 48, 36, 12
- GCF
- 12
- LCM
- 144
- Common factors
- 6
Greatest Common Factor (GCF)
3 integers
Every input is divisible by 12. This is the largest such divisor.
Prime factorisation
Factor each number — the GCF uses the minimum exponents
Indigo prime factors appear in every input; the GCF takes the minimum exponent for each.
Common factors
All divisors of 12 — shared by every input
Every number in the input is evenly divisible by each of these 6 values. The largest is the GCF.
Algorithm
Euclidean algorithm — step by step
gcd(48, 36)
- 148 = 1 × 36 + 12
- 236 = 3 × 12 + 0← remainder = 0
gcd(48, 36) = 12
gcd(12, 12) — continuing with result
- 112 = 1 × 12 + 0← remainder = 0
gcd(12, 12) = 12
Field guide
What is the GCF and how do you find it — two complete methods.
The Greatest Common Factor (GCF): also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) — of two or more integers is the largest positive integer that divides all of them without a remainder. Understanding the GCF is foundational to arithmetic: it unlocks fraction simplification, algebra, and number theory.
Method 1: Euclid's algorithm
The Euclidean algorithm is the fastest practical method and the one used by this calculator. Published by Euclid around 300 BCE in the Elements, it remains one of the oldest algorithms still in everyday use. The key insight:
The algorithm repeats this substitution until the remainder reaches zero. The last non-zero remainder is the GCF.
Worked example: gcd(48, 18):
- 48 = 2 × 18 + 12 → remainder 12
- 18 = 1 × 12 + 6 → remainder 6
- 12 = 2 × 6 + 0 → remainder 0; stop
The last non-zero remainder is 6, so gcd(48, 18) = 6. The algorithm terminates in at most O(log(min(a, b))) steps — extremely fast even for very large numbers.
For more than two numbers, apply the algorithm iteratively from left to right: gcd(a, b, c) = gcd(gcd(a, b), c).
Method 2: prime factorisation
Decompose each number into its prime factors, then multiply together the common primes at their minimum exponent:
18 = 2¹ × 3²
GCF = 2^min(4,1) × 3^min(1,2) = 2¹ × 3¹ = 6
This method is intuitive and clearly shows which primes contribute to the GCF, but it is slower than Euclid's algorithm for large numbers because finding prime factors requires trial division up to √n.
Coprime numbers (GCF = 1)
When two or more numbers share no common factor greater than 1, their GCF equals 1 and the numbers are called coprime (or mutually prime, or relatively prime). Examples: 8 and 9 are coprime (gcd = 1), as are any two distinct prime numbers. Coprimality is important in cryptography (RSA algorithm) and modular arithmetic.
GCF vs. LCM: the fundamental identity
The Greatest Common Factor and Least Common Multiple of any two positive integers are related by a clean identity:
Therefore: LCM(a, b) = (a × b) / GCF(a, b). This is by far the most efficient way to compute the LCM once the GCF is known, since it avoids the potentially massive direct computation of LCM from scratch.
Example: a = 48, b = 18, GCF = 6. LCM = (48 × 18) / 6 = 864 / 6 = 144.
Practical applications of the GCF
- Simplifying fractions. To reduce 36/48 to lowest terms: GCF(36, 48) = 12. Divide numerator and denominator by 12: 3/4. The fraction is in lowest terms when the GCF of the numerator and denominator is 1.
- Distributing evenly. You have 48 apples and 36 oranges. The maximum number of identical fruit baskets you can make (same number of each fruit, no leftovers) is GCF(48, 36) = 12.
- Tiling problems. A rectangular floor 48 × 36 cm tiled with identical squares — the largest square that fits perfectly has a side length of GCF(48, 36) = 12 cm.
- Algebraic simplification. To simplify the polynomial expression 12x² + 18x + 6, factor out the GCF(12,18,6) = 6 to get 6(2x² + 3x + 1).
- Cryptography. RSA key generation requires that the totient of n is coprime with the public exponent e — directly checking GCF(e, φ(n)) = 1 using Euclid's algorithm.
- Time and scheduling. Two events occur every 12 and 18 days respectively. They coincide every LCM(12, 18) = 36 days — computed via the GCF.
Properties of the GCF
| Property | Rule | Example |
|---|---|---|
| Commutative | gcd(a, b) = gcd(b, a) | gcd(12, 8) = gcd(8, 12) = 4 |
| Associative | gcd(a, gcd(b, c)) = gcd(gcd(a,b), c) | gcd(12, gcd(8, 6)) = 2 |
| Identity | gcd(a, 0) = a | gcd(12, 0) = 12 |
| Idempotent | gcd(a, a) = a | gcd(7, 7) = 7 |
| Divisibility | gcd(a, b) divides both a and b | gcd(12, 8) = 4; 4|12 and 4|8 |
| Linear combo | gcd(a,b) = xa + yb for some x,y | gcd(12,8)=4 = 1×12 + (−1)×8 |
Why Euclid's algorithm terminates and is correct
Termination: At each step, the second argument strictly decreases (it becomes the remainder, which is always less than the divisor). Since all values are non-negative integers, the sequence of remainders must eventually reach 0.
Correctness: The key insight is that for any a and b, gcd(a, b) = gcd(b, r) where r = a mod b. This follows from the fact that any common divisor of a and b also divides r (= a − qb), and any common divisor of b and r also divides a (= qb + r). So the two pairs share exactly the same set of common divisors and hence the same greatest common divisor.
Extended Euclidean algorithm (Bézout's identity)
The extended Euclidean algorithm finds integers x and y such that:
For example, gcd(48, 18) = 6 = 48(1) + 18(−2). This extension is used in modular arithmetic to find multiplicative inverses and is the foundation of RSA encryption, the Chinese Remainder Theorem, and Diophantine equation solving.