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.
What is GCD?
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.
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.
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.
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 can be covered by 3×5=15 such tiles with no gaps or overlaps.
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.