When two numbers share common factors, the greatest among them captures the deepest structural connection between the pair. The greatest common divisor — GCD — measures how much two numbers overlap in their factor structure, and it appears everywhere from simplifying fractions to determining whether two quantities are fundamentally incompatible.
The greatest common divisor of two positive integers a and b, written gcd(a,b), is the largest positive integer that divides both.
The common factors of 12 and 18 are {1,2,3,6}. The largest is 6, so gcd(12,18)=6.
The common factors of 20 and 35 are {1,5}. The largest is 5, so gcd(20,35)=5.
The GCD always exists for any pair of positive integers, and it is always at least 1 — because 1 divides everything. It can never exceed the smaller of the two numbers, since no factor of a can be larger than a itself.
The same concept goes by several names. GCD (greatest common divisor) is standard in most mathematical texts. HCF (highest common factor) is common in British usage. GCF (greatest common factor) appears in some textbooks. All three refer to the same quantity.
Basic Properties
Several properties follow directly from the definition and hold for all positive integers.
gcd(a,a)=a. The largest number dividing a and a is a itself.
gcd(a,1)=1. The only positive divisor of 1 is 1, so the only common divisor is 1.
gcd(a,0)=a. Every positive integer divides 0, so the common divisors of a and 0 are exactly the divisors of a. The largest is a.
gcd(a,b)=gcd(b,a). Order is irrelevant — the common factors of a and b are the same as those of b and a.
gcd(a,b)≤min(a,b). No common divisor can exceed the smaller number.
One further property connects the GCD to all other common divisors: every common divisor of a and b also divides gcd(a,b). The GCD is not just the largest common divisor — it is a multiple of every common divisor.
Property
Statement
Example
Reflexivity & identities
gcd(a, a) = a; gcd(a, 1) = 1; gcd(a, 0) = a
gcd(7, 7) = 7; gcd(15, 1) = 1; gcd(15, 0) = 15
Commutativity
gcd(a, b) = gcd(b, a)
gcd(12, 18) = gcd(18, 12) = 6
Upper bound
gcd(a, b) ≤ min(a, b)
gcd(12, 18) = 6 ≤ min(12, 18) = 12
Universal divisibility
every common divisor of a and b also divides gcd(a, b)
common divisors of 12 and 18 are 1, 2, 3, 6 — and every one divides gcd = 6
Method 1: Listing Factors
The most direct approach finds all factors of each number, identifies the overlap, and selects the largest.
For gcd(24,36):
Factors of 24: {1,2,3,4,6,8,12,24}.
Factors of 36: {1,2,3,4,6,9,12,18,36}.
Common factors: {1,2,3,4,6,12}.
The largest is 12, so gcd(24,36)=12.
The method is transparent and reliable for small numbers. For large numbers it becomes impractical — finding all factors of a number like 1,764 requires systematic testing up to 1764≈42, and doing this for two numbers is tedious. The methods that follow avoid listing factors entirely.
Method 2: Prime Factorization
The prime factorization of each number reveals exactly which primes they share and in what quantities. The GCD takes the minimum exponent for each common prime.
For gcd(48,180):
48=24⋅31
180=22⋅32⋅51
The primes appearing in both factorizations are 2 and 3. The prime 5 appears only in 180 and contributes nothing to the GCD.
Take the smaller exponent for each shared prime: min(4,2)=2 for the prime 2, and min(1,2)=1 for the prime 3.
gcd(48,180)=22⋅31=4⋅3=12
This method is efficient when the factorizations are easy to find. For numbers whose prime factors are not immediately apparent, the Euclidean algorithm is faster.
Method 3: Euclidean Algorithm
The Euclidean algorithm computes the GCD without factoring either number. It relies on a single property: gcd(a,b)=gcd(b,amodb). Replacing the larger number with the remainder of their division preserves the GCD while shrinking the problem.
For gcd(252,105):
252=105⋅2+42, so gcd(252,105)=gcd(105,42).
105=42⋅2+21, so gcd(105,42)=gcd(42,21).
42=21⋅2+0, so gcd(42,21)=21.
The last nonzero remainder is 21, which is gcd(252,105).
The algorithm works because any common divisor of a and b is also a common divisor of b and amodb. The modulo operation peels away multiples of b from a, leaving a smaller number with the same common divisor structure. This is the most efficient of the three methods, particularly for large numbers where factorization is difficult.
Euclidean Algorithm Step by Step
The procedure is mechanical. Start with two positive integers a and b, with a≥b.
Compute r=amodb. Replace a with b and b with r. Repeat until b=0. The value of a at that point is the GCD.
For gcd(462,198):
462=198⋅2+66→a=198,b=66
198=66⋅3+0→b=0
gcd(462,198)=66.
For gcd(1,071,462):
1071=462⋅2+147→a=462,b=147
462=147⋅3+21→a=147,b=21
147=21⋅7+0→b=0
gcd(1071,462)=21.
The algorithm always terminates because the remainder r satisfies 0≤r<b, so b strictly decreases at each step. A sequence of positive integers that strictly decreases must eventually reach zero.
Two numbers are coprime — also called relatively prime — when their GCD is 1. They share no common factor except the trivial one.
The numbers 8 and 15 are coprime: the factors of 8 are {1,2,4,8}, the factors of 15 are {1,3,5,15}, and the only overlap is 1.
The numbers 9 and 12 are not coprime: gcd(9,12)=3.
The numbers 7 and 20 are coprime: 7 is prime and does not divide 20.
Two structural facts generate coprime pairs reliably. Any two consecutive integers are coprime — gcd(n,n+1)=1 for all n — because any common divisor of n and n+1 would have to divide their difference, which is 1. And a prime p is coprime with every number it does not divide.
Properties of Coprime Numbers
Coprimality enables conclusions that fail for numbers with shared factors.
If gcd(a,b)=1 and a∣(b⋅c), then a∣c. When a and b share no common factor, the factor a hiding inside the product b⋅c must come entirely from c. Without coprimality, this inference breaks — 6∣(4⋅3) does not imply 6∣3.
If gcd(a,b)=1 and gcd(a,c)=1, then gcd(a,b⋅c)=1. Coprimality with individual factors extends to their product.
If gcd(a,b)=1, then gcd(a2,b2)=1. Squaring both numbers introduces no new shared primes.
These properties are essential in the theory of divisibility. The rule that divisibility by 6 can be tested by checking 2 and 3 separately works precisely because gcd(2,3)=1. Coprimality is what makes the combined divisibility rules valid.
Property
Statement
Example
Euclid's lemma
if gcd(a, b) = 1 and a ∣ (b · c), then a ∣ c
gcd(7, 15) = 1 and 7 ∣ (15 · 21 = 315), so 7 ∣ 21 ✓
Coprimality with a product
if gcd(a, b) = 1 and gcd(a, c) = 1, then gcd(a, b · c) = 1
gcd(5, 4) = 1 and gcd(5, 9) = 1, so gcd(5, 36) = 1 ✓
Coprimality under powers
if gcd(a, b) = 1, then gcd(an, bn) = 1 for every n ≥ 1
gcd(8, 15) = 1, so gcd(64, 225) = 1 ✓
GCD of More Than Two Numbers
The GCD extends to any number of inputs by applying it pairwise. The key identity is:
gcd(a,b,c)=gcd(gcd(a,b),c)
Compute the GCD of the first two numbers, then take the GCD of that result with the third number. The process chains to any length.
For gcd(24,36,60):
gcd(24,36)=12.
gcd(12,60)=12.
So gcd(24,36,60)=12.
For gcd(18,30,42):
gcd(18,30)=6.
gcd(6,42)=6.
So gcd(18,30,42)=6.
The order of pairing does not matter — the GCD is associative and commutative, so any grouping produces the same result.
Applications of GCD
The most immediate application is simplifying fractions. The fraction 3624 reduces to 32 by dividing numerator and denominator by gcd(24,36)=12. A fraction is in lowest terms when the GCD of its numerator and denominator is 1.
Ratios simplify the same way. A rectangle with dimensions 48×80 has an aspect ratio of 48:80. Dividing both by gcd(48,80)=16 gives 3:5, as the figure below shows.
Tiling problems use the GCD geometrically. The largest square tile that fits perfectly into a 48×80 rectangle has side length gcd(48,80)=16. The rectangle is then covered by 3×5=15 such tiles with no gaps or overlaps, as shown below.
The GCD also connects to the LCM through a clean identity: a⋅b=gcd(a,b)⋅lcm(a,b). Knowing the GCD gives the LCM for free, and vice versa.
Worked Examples
Find gcd(56,84) by listing factors. Factors of 56: {1,2,4,7,8,14,28,56}. Factors of 84: {1,2,3,4,6,7,12,14,21,28,42,84}. Common: {1,2,4,7,14,28}. GCD =28.
Find gcd(120,84) by prime factorization. 120=23⋅3⋅5 and 84=22⋅3⋅7. Shared primes: 2min(3,2)⋅3min(1,1)=22⋅3=12.
Find gcd(782,253) by the Euclidean algorithm. 782=253⋅3+23. Then 253=23⋅11+0. GCD =23.
Are 35 and 54 coprime? gcd(35,54): 54=35⋅1+19, 35=19⋅1+16, 19=16⋅1+3, 16=3⋅5+1, 3=1⋅3+0. GCD =1. Yes, coprime.
Simplify 12684. gcd(84,126): 126=84⋅1+42, 84=42⋅2+0. GCD =42. The fraction reduces to 32.
Summary: Three Methods for GCD
Three routes lead to the same destination, each preferable in different situations. Listing factors is transparent for small numbers but quickly impractical; prime factorization is efficient when factor structures are accessible; the Euclidean algorithm avoids factoring entirely and stays fast even for very large numbers. The table below collects all three side by side — the kind of inputs each handles best, the mechanics in one line, and a worked example.
Method
Best for
How it works
Worked example
Listing factors
small inputs; transparent for teaching
list all factors of each number, intersect the lists, take the largest
gcd(24, 36): factors of 24 = {1,2,3,4,6,8,12,24}, factors of 36 = {1,2,3,4,6,9,12,18,36} → common = {1,2,3,4,6,12} → 12
Prime factorization
factorizations are easy to obtain or already known
factor both numbers; for each prime, take the minimum exponent appearing in either factorization