How to Find the Greatest Common Divisor (GCD)
The greatest common divisor (GCD) of two or more integers is the largest integer that divides all of them exactly. This page explains three methods for finding GCD — listing factors, prime factorization, and the Euclidean algorithm — with worked examples for each.
Definition
GCD(a, b) is the largest positive integer d such that d divides a and d divides b with no remainder. The same concept is also called HCF (highest common factor) or GCF (greatest common factor).
Method 1 — Listing Factors
List all factors of each number and find the largest one they share. This method is practical only for small numbers.
| Number | Factors |
|---|---|
| 48 | 1, 2, 3, 4, 6, 8, 12, 16, 24, 48 |
| 36 | 1, 2, 3, 4, 6, 9, 12, 18, 36 |
| Common factors | 1, 2, 3, 4, 6, 12 |
| GCD | 12 |
Method 2 — Prime Factorization
Write each number as a product of prime powers. The GCD is the product of shared primes, each raised to the minimum exponent.
Example: GCD(360, 756)
| Prime | Exponent in 360 | Exponent in 756 | min → used in GCD |
|---|---|---|---|
| 2 | 3 | 2 | 2 |
| 3 | 2 | 3 | 2 |
| 5 | 1 | 0 | 0 (excluded) |
| 7 | 0 | 1 | 0 (excluded) |
Method 3 — Euclidean Algorithm
The Euclidean algorithm is the fastest method, especially for large numbers. It is based on the property that GCD(a, b) = GCD(b, a mod b).
- If b = 0, then GCD = a. Stop.
- Compute remainder r = a mod b.
- Set a = b and b = r.
- Repeat from step 1.
Worked Example: GCD(252, 105)
| Step | a | b | a = b × q + r | Remainder r |
|---|---|---|---|---|
| 1 | 252 | 105 | 252 = 105 × 2 + 42 | 42 |
| 2 | 105 | 42 | 105 = 42 × 2 + 21 | 21 |
| 3 | 42 | 21 | 42 = 21 × 2 + 0 | 0 |
Remainder reaches 0. The GCD is the last non-zero remainder: GCD(252, 105) = 21.
Worked Example: GCD(1071, 462)
| Step | a | b | a = b × q + r | Remainder r |
|---|---|---|---|---|
| 1 | 1071 | 462 | 1071 = 462 × 2 + 147 | 147 |
| 2 | 462 | 147 | 462 = 147 × 3 + 21 | 21 |
| 3 | 147 | 21 | 147 = 21 × 7 + 0 | 0 |
GCD(1071, 462) = 21.
GCD of More Than Two Numbers
Apply GCD pairwise using the associative property:
Example: GCD(12, 18, 24) → GCD(GCD(12, 18), 24) = GCD(6, 24) = 6.
Key Properties of GCD
| Property | Statement | 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) | — |
| Identity | GCD(a, 0) = a | GCD(7, 0) = 7 |
| GCD × LCM | GCD(a, b) × LCM(a, b) = a × b | 4 × 24 = 8 × 12 = 96 |
| Coprime | If GCD(a, b) = 1, a and b are coprime | GCD(8, 15) = 1 |
Applications
- Simplifying fractions: divide numerator and denominator by their GCD.
- Solving linear Diophantine equations: ax + by = c has integer solutions if and only if GCD(a, b) divides c.
- RSA cryptography: the extended Euclidean algorithm computes modular inverses for key generation.
- Computer science: used in algorithms for least common multiple, modular arithmetic, and hash functions.
- GCD Calculator — Calculate GCD with step-by-step Euclidean algorithm output
- GCD Formula Reference — Euclidean algorithm formula, variables, and worked examples
Frequently Asked Questions
What is the GCD of a number and itself?
GCD(a, a) = a. Any number divides itself, so it is its own GCD. For example, GCD(7, 7) = 7.
Why does the Euclidean algorithm work?
It works because GCD(a, b) = GCD(b, a mod b). Any common divisor of a and b also divides a mod b (since a mod b = a − b × ⌊a/b⌋). So the set of common divisors is unchanged at each step.
How fast is the Euclidean algorithm?
It runs in O(log min(a, b)) steps. The number of steps is at most 5 times the number of decimal digits in the smaller number (Lamé's theorem). In practice it is extremely fast even for very large integers.
What is the extended Euclidean algorithm?
The extended version also finds integers x and y such that ax + by = GCD(a, b). This is called Bézout's identity and is the foundation of modular inverse computation used in RSA encryption.
Is GCD defined for negative numbers?
By convention, GCD is defined for positive integers. When applied to negative numbers, it is typically defined as GCD(|a|, |b|) — the GCD of their absolute values.