What is the greatest common divisor (GCD)?

The GCD of two positive integers a and b is the largest positive integer that divides both. For example, gcd(12, 18) = 6 because 6 is the largest number that divides both 12 and 18 evenly.

What is the difference between GCD, HCF, and GCF?

They are all the same concept with different names. GCD (greatest common divisor) is standard in mathematics. HCF (highest common factor) is common in British usage. GCF (greatest common factor) appears in some textbooks.

How do you find the GCD by listing factors?

List all factors of each number, find the common factors (numbers appearing in both lists), and select the largest. For gcd(24, 36): factors of 24 are {1,2,3,4,6,8,12,24}, factors of 36 are {1,2,3,4,6,9,12,18,36}, common factors are {1,2,3,4,6,12}, so GCD = 12.

How do you find the GCD using prime factorization?

Factor both numbers into primes, identify shared primes, and take the minimum exponent for each. For gcd(48, 180): 48 = 2⁴×3¹ and 180 = 2²×3²×5¹. Shared primes: 2^min(4,2) × 3^min(1,2) = 2²×3 = 12.

What is the Euclidean algorithm?

A method to find GCD without factoring. Use the property gcd(a,b) = gcd(b, a mod b). Repeatedly replace (a,b) with (b, a mod b) until b=0. The final value of a is the GCD. For gcd(252,105): 252=105×2+42, 105=42×2+21, 42=21×2+0, so GCD=21.

What does coprime (relatively prime) mean?

Two numbers are coprime when their GCD is 1 — they share no common factor except 1. For example, 8 and 15 are coprime because gcd(8,15)=1. Any two consecutive integers are always coprime.

Why are coprime numbers important?

Coprimality enables key divisibility properties. If gcd(a,b)=1 and a divides b×c, then a must divide c. This is why divisibility by 6 can be tested by checking 2 and 3 separately — because gcd(2,3)=1.

How do you find the GCD of more than two numbers?

Apply GCD pairwise: gcd(a,b,c) = gcd(gcd(a,b), c). For gcd(24,36,60): first gcd(24,36)=12, then gcd(12,60)=12. The order doesn't matter — GCD is associative and commutative.

How is GCD used to simplify fractions?

Divide both numerator and denominator by their GCD. For 84/126: gcd(84,126)=42, so 84/126 = (84÷42)/(126÷42) = 2/3. A fraction is in lowest terms when gcd(numerator, denominator) = 1.

What is the relationship between GCD and LCM?

For any two positive integers a and b: a × b = gcd(a,b) × lcm(a,b). This means if you know the GCD, you can find the LCM by computing (a×b)/gcd(a,b), and vice versa.

Which method for finding GCD is most efficient?

The Euclidean algorithm is most efficient, especially for large numbers. It requires no factorization and terminates quickly because the remainder strictly decreases at each step. Listing factors or finding prime factorizations is slower for large numbers.

Greatest Common Divisor (GCD)

Key Terms

What is GCD?

Basic Properties

Method 1: Listing Factors

Method 2: Prime Factorization

Method 3: Euclidean Algorithm

Euclidean Algorithm Step by Step

Coprime (Relatively Prime) Numbers

Properties of Coprime Numbers

GCD of More Than Two Numbers

Applications of GCD

Worked Examples

Summary: Three Methods for GCD

The Largest Shared Divisor

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.

Key Terms

Greatest Common Divisor— the central concept on this page

Coprime— two integers whose GCD is 1; covered in detail here

Prime Factorization— one of three methods for computing the GCD

Least Common Multiple— linked to the GCD by a clean identity

See All Arithmetic Definitions →

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

a

itself.

\gcd(a, 1) = 1

. The only positive divisor of

1

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) \leq \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

\sqrt{1764} \approx 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 = 2^4 \cdot 3^1

180 = 2^2 \cdot 3^2 \cdot 5^1

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) = 2^2 \cdot 3^1 = 4 \cdot 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, \; a \bmod b)

. Replacing the larger number with the remainder of their division preserves the GCD while shrinking the problem.

For

\gcd(252, 105)

252 = 105 \cdot 2 + 42

, so

\gcd(252, 105) = \gcd(105, 42)

105 = 42 \cdot 2 + 21

, so

\gcd(105, 42) = \gcd(42, 21)

42 = 21 \cdot 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

a \bmod b

. 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 \geq b

.

Compute

r = a \bmod b

. 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 \cdot 2 + 66 \quad \to \quad a = 198, \; b = 66

198 = 66 \cdot 3 + 0 \quad \to \quad b = 0

\gcd(462, 198) = 66

.

For

\gcd(1{,}071, 462)

1071 = 462 \cdot 2 + 147 \quad \to \quad a = 462, \; b = 147

462 = 147 \cdot 3 + 21 \quad \to \quad a = 147, \; b = 21

147 = 21 \cdot 7 + 0 \quad \to \quad b = 0

\gcd(1071, 462) = 21

.

The algorithm always terminates because the remainder

r

satisfies

0 \leq r < b

, so

b

strictly decreases at each step. A sequence of positive integers that strictly decreases must eventually reach zero.

Try calculating Greatest Common Divisor with our GCF Calculator →

Coprime (Relatively Prime) Numbers

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 \mid (b \cdot c)

, then

a \mid c

. When

a

and

b

share no common factor, the factor

a

hiding inside the product

b \cdot c

must come entirely from

c

. Without coprimality, this inference breaks —

6 \mid (4 \cdot 3)

does not imply

6 \mid 3

.

If

\gcd(a, b) = 1

and

\gcd(a, c) = 1

, then

\gcd(a, b \cdot c) = 1

. Coprimality with individual factors extends to their product.

If

\gcd(a, b) = 1

, then

\gcd(a^2, b^2) = 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(aⁿ, bⁿ) = 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

\frac{24}{36}

reduces to

\frac{2}{3}

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 \times 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 \times 80

rectangle has side length

\gcd(48, 80) = 16

. The rectangle can be covered by

3 \times 5 = 15

such tiles with no gaps or overlaps.

The GCD also connects to the LCM through a clean identity:

a \cdot b = \gcd(a, b) \cdot \text{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 = 2^3 \cdot 3 \cdot 5

and

84 = 2^2 \cdot 3 \cdot 7

. Shared primes:

2^{\min(3,2)} \cdot 3^{\min(1,1)} = 2^2 \cdot 3 = 12

.

Find

\gcd(782, 253)

by the Euclidean algorithm.

782 = 253 \cdot 3 + 23

. Then

253 = 23 \cdot 11 + 0

. GCD

= 23

.

Are

35

and

54

coprime?

\gcd(35, 54)

54 = 35 \cdot 1 + 19

35 = 19 \cdot 1 + 16

19 = 16 \cdot 1 + 3

16 = 3 \cdot 5 + 1

3 = 1 \cdot 3 + 0

. GCD

= 1

. Yes, coprime.

Simplify

\frac{84}{126}

\gcd(84, 126)

126 = 84 \cdot 1 + 42

84 = 42 \cdot 2 + 0

. GCD

= 42

. The fraction reduces to

\frac{2}{3}

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	gcd(48, 180): 48 = 2⁴ · 3, 180 = 2² · 3² · 5 → 2² · 3 = 12
Euclidean algorithm	large numbers; factorization difficult; most efficient overall	repeatedly replace (a, b) with (b, a mod b) — using the modulo operation — until b = 0; the final nonzero a is the gcd	gcd(252, 105): 252 = 105·2 + 42, 105 = 42·2 + 21, 42 = 21·2 + 0 → 21