Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools


Greatest Common Divisor (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?

Two ribbons, 12 cm and 18 cm long, are to be cut into pieces of one equal length with nothing left over. How long can the pieces be?
A piece length works only if it fits a whole number of times into both ribbons. Long pieces are better — fewer cuts — so the question is which length is the longest that works.
Trying lengths one by one: 1, 2, 3 and 6 cm work for both ribbons; 4 and 9 cm leave a leftover.
piece length (cm)pieces from 12 cmpieces from 18 cmworks for both?
11218yes
269yes
346yes
434.5 — leftoverno
623yes — the longest
91.33… — leftover2no
Lengths from 77 to 1111 cm leave a leftover in the 1212 cm ribbon, and a 1212 cm piece does not fit into 1818 cm a whole number of times, so 66 cm is the longest length that works.
The lengths that work are exactly the numbers that divide both 12 and 18 — and the answer is the largest of them.
The common factors of 1212 and 1818 are {1,2,3,6}\{1, 2, 3, 6\}. The largest is 66, so gcd⁡(12,18)=6\gcd(12, 18) = 6.
Common factors of two numbersfactors of 121234612factors of 181236918gcd(12, 18) = 6largest common factorcommon factors of 12 and 18{1, 2, 3, 6}gcd(12, 18) = 6
The definition
The greatest common divisor of two positive integers is the largest positive integer that divides both of them.
The greatest common divisor of two positive integers aa and bb, written gcd⁡(a,b)\gcd(a, b), is the largest positive integer that divides both.
So gcd⁡(12,18)=6\gcd(12, 18) = 6: the ribbons are cut into 66 cm pieces, two from one and three from the other.
The GCD is one number attached to a pair of numbers, and every pair has one.
The common factors of 2020 and 3535 are {1,5}\{1, 5\}. The largest is 55, so gcd⁡(20,35)=5\gcd(20, 35) = 5.
The GCD always exists for any pair of positive integers, and it is always at least 11 — because 11 divides everything. It can never exceed the smaller of the two numbers, since no factor of aa can be larger than aa 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.
The greatest common divisor is not the least common multiple — one divides the numbers, the other is divided by them.
Pitfall: Confusing the GCD with the LCM
Giving 3636 as gcd⁡(12,18)\gcd(12, 18) answers a different question: 3636 is the least common multiple, a number that 1212 and 1818 both divide. The GCD divides both numbers, so it is 66.
For large numbers, listing every divisor is slow; the Euclidean algorithm finds the GCD in a few steps.
The rest of the page covers notation, basic properties, three methods — listing factors, prime factorization, the Euclidean algorithm — coprime numbers, the GCD of more than two numbers, and applications.

GCD Notation

Notation

GCD Notation

A function spelling, an acronym zoo, and an equation that doubles as a definition — the marks behind every greatest-common-divisor statement on this page and its siblings.
The divides bar a∣ba \mid b inside every argument is owned by divisibility notation; lcm⁡(a,b)\operatorname{lcm}(a, b), the mirror twin, by the LCM page.
gcd⁡(a,b)\gcd(a, b)
the g-c-d of a and b
Function spelling for a number-theoretic quantity: lowercase upright gcd⁡\gcd, arguments in parentheses — the same grammar as function notation, applied to a count. What is GCD? above defines the value.
CasesMore arguments, same mark — gcd⁡(a,b,c)\gcd(a, b, c), evaluated pairwise in any order, as GCD of More Than Two Numbers below shows; the twin lcm⁡(a,b)\operatorname{lcm}(a, b) is tied to it by gcd⁡(a,b)⋅lcm⁡(a,b)=a⋅b\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b.
Also written(a,b)(a, b) — number theory's bare-parentheses shorthand, gcd⁡(12,18)\gcd(12, 18) compressed to (12,18)(12, 18); compact but triple-booked, since the same glyphs write points, open intervals, and ordered pairs.
Do not confuseA product of letters. gcd⁡\gcd is typeset upright as one operator name — italic GCD(a,b)GCD(a, b) in math mode reads as G⋅C⋅DG \cdot C \cdot D, the same multi-letter misreading the trig abbreviations fight.
GCD ⋅ HCF ⋅ GCF\text{GCD · HCF · GCF}
greatest common divisor; highest common factor; greatest common factor
One quantity, three acronyms: GCD standard in mathematical texts, HCF in British and Indian curricula, GCF in American school textbooks — What is GCD? above lists all three. The choice signals the audience, never the value.
CasesTranslation is the skill — an HCF exam problem and a gcd⁡\gcd formula are the same mathematics; calculators settle it with a gcd( key almost universally.
Do not confuseDifferent quantities. Meeting HCF after GCD suggests a new concept — but "highest"/"greatest" and "factor"/"divisor" are synonym pairs, not distinctions.
gcd⁡(a,b)=1\gcd(a, b) = 1
a and b are coprime
An equation doing definition duty: coprimality has no dedicated mark on this site — the statement gcd⁡(a,b)=1\gcd(a, b) = 1 is the notation, read directly as "coprime" or "relatively prime", per Coprime (Relatively Prime) Numbers below.
CasesThe idiom powers lowest-terms tests — 35\frac{3}{5} is reduced because gcd⁡(3,5)=1\gcd(3, 5) = 1, the equivalent fractions criterion; some number-theory texts abbreviate to a⊥ba \perp b, the perpendicularity glyph borrowed sideways.
Do not confusePrimality. Coprime is a relationship between two numbers, prime a property of one — 88 and 1515 are coprime though neither is prime; the pair-ness lives in the notation's two arguments.
DownloadPNG2×PDF
Notation · Cheat sheet
Arithmetic Notation at a Glance
The marks from the notation cards across the arithmetic pages: how each is read and what it means. Every group links to the full card on its page.
Fractions
ab\frac{a}{b}
a over b
The vinculum: numerator over denominator, a division held in place.
a/ba/b
a slash b; a over b
The inline spelling for running text and code; same value, no grouping power.
a÷ba \div b
a divided by b
The obelus, the schoolroom division sign: a÷b=aba \div b = \frac{a}{b}.
Mixed numbers
2342\frac{3}{4}
two and three quarters
Adjacency means addition here, and only here: 2+342 + \frac{3}{4}.
3543\frac{5}{4} vs 4144\frac{1}{4}
non-standard form, and its correction
The fractional part must be proper; carry the extra whole.
−234-2\frac{3}{4}
negative two and three quarters
The minus grips the whole package: −(2+34)-(2 + \frac{3}{4}).
Divisibility
a∣ba \mid b
a divides b
A statement, true or false: b=a⋅kb = a \cdot k for some integer kk.
5∤125 \nmid 12
five does not divide twelve
The slashed bar denies: no integer kk gives 12=5k12 = 5k.
b mod a=0b \bmod a = 0
b mod a equals zero
The same fact as a computation: the remainder vanishes.
Factors
n=p1a1⋯pkakn = p_1^{a_1} \cdots p_k^{a_k}
n as a product of prime powers
Canonical factorisation: pp for primes, exponents count repeats.
d(n)d(n) · τ(n)\tau(n)
d of n; tau of n
The number of positive divisors of nn.
σ(n)\sigma(n)
sigma of n
The sum of the positive divisors: σ(12)=28\sigma(12) = 28.
GCDThis page
gcd⁡(a,b)\gcd(a, b)
the g-c-d of a and b
Greatest common divisor, in function spelling.
HCF, GCF\text{HCF, GCF}
highest, or greatest, common factor
Other names for the gcd: HCF in British and Indian schools, GCF in American schools.
gcd⁡(a,b)=1\gcd(a, b) = 1
a and b are coprime
The equation is the notation; coprimality has no mark of its own.
LCM
lcm⁡(a,b)\operatorname{lcm}(a, b)
the l-c-m of a and b
Least common multiple, the mirror twin of gcd⁡\gcd.
[a,b][a, b]
bracket a, b
Number theory’s shorthand for the lcm; (a,b)(a, b) is the gcd.
LCM vs LCD\text{LCM vs LCD}
least common multiple; least common denominator
The LCD of fractions is the LCM of their denominators.
Modulo
a mod na \bmod n
a mod n
The operator that computes a remainder: 17 mod 5=217 \bmod 5 = 2.
a % na \ \% \ n
a percent n
The remainder operator in code: C, Java, Python, JavaScript.
a≡b(modn)a \equiv b \pmod{n}
a is congruent to b modulo n
A statement: aa and bb leave the same remainder.
Integer part
⌊x⌋\lfloor x \rfloor
floor of x
The greatest integer at most xx: the integer part.
⌈x⌉\lceil x \rceil
ceiling of x
The least integer at least xx.
{x}\{x\}
fractional part of x
What the floor leaves: x−⌊x⌋x - \lfloor x \rfloor, in [0,1)[0, 1).
⌊x+12⌋\lfloor x + \tfrac{1}{2} \rfloor
x rounded to the nearest integer
Rounding built from the floor; ties go up: 2.5→32.5 \to 3.
Same marks, different job
a∣ba \mid bDivides, between integers; such that, inside set braces; absolute value when doubled.
(a,b)(a, b) vs [a,b][a, b]The gcd and the lcm in number-theory shorthand; a point or an interval elsewhere.
{x}\{x\}The fractional part here; a one-element set in set theory.
 mod \bmod vs (modn)\pmod{n}An operator that returns a number; a label on a congruence statement.
σ(n)\sigma(n)The divisor sum here; a standard deviation in statistics.
Arithmetic Notation at a Glance·/arithmeticLearn Math Class

Basic Properties

Several properties follow directly from the definition and hold for all positive integers.

gcd⁡(a,a)=a\gcd(a, a) = a. The largest number dividing aa and aa is aa itself.

gcd⁡(a,1)=1\gcd(a, 1) = 1. The only positive divisor of 11 is 11, so the only common divisor is 11.

gcd⁡(a,0)=a\gcd(a, 0) = a. Every positive integer divides 00, so the common divisors of aa and 00 are exactly the divisors of aa. The largest is aa.

gcd⁡(a,b)=gcd⁡(b,a)\gcd(a, b) = \gcd(b, a). Order is irrelevant — the common factors of aa and bb are the same as those of bb and aa.

gcd⁡(a,b)≤min⁡(a,b)\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 aa and bb also divides gcd⁡(a,b)\gcd(a, b). The GCD is not just the largest common divisor — it is a multiple of every common divisor.
DownloadPNG2×PDF
Layout
PropertyStatementExample
Reflexivity & identitiesgcd(a, a) = a; gcd(a, 1) = 1; gcd(a, 0) = agcd(7, 7) = 7; gcd(15, 1) = 1; gcd(15, 0) = 15
Commutativitygcd(a, b) = gcd(b, a)gcd(12, 18) = gcd(18, 12) = 6
Upper boundgcd(a, b) ≤ min(a, b)gcd(12, 18) = 6 ≤ min(12, 18) = 12
Universal divisibilityevery 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
Basic PropertiesLearn Math Class

Method 1: Listing Factors

The most direct approach finds all factors of each number, identifies the overlap, and selects the largest.

Example
For gcd⁡(24,36)\gcd(24, 36):
Factors of 2424: {1,2,3,4,6,8,12,24}\{1, 2, 3, 4, 6, 8, 12, 24\}.
Factors of 3636: {1,2,3,4,6,9,12,18,36}\{1, 2, 3, 4, 6, 9, 12, 18, 36\}.
Common factors: {1,2,3,4,6,12}\{1, 2, 3, 4, 6, 12\}.
The largest is 1212, so gcd⁡(24,36)=12\gcd(24, 36) = 12.
Common factors of two numbersfactors of 241234681224factors of 36123469121836gcd(24, 36) = 12largest common factorcommon factors of 24 and 36{1, 2, 3, 4, 6, 12}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,7641{,}764 requires systematic testing up to 1764=42\sqrt{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.

RULE
The GCD takes the minimum exponent for each common prime.

For gcd⁡(48,180)\gcd(48, 180):

48=24⋅3148 = 2^4 \cdot 3^1

180=22⋅32⋅51180 = 2^2 \cdot 3^2 \cdot 5^1

The primes appearing in both factorizations are 22 and 33. The prime 55 appears only in 180180 and contributes nothing to the GCD.

Take the smaller exponent for each shared prime: min⁡(4,2)=2\min(4, 2) = 2 for the prime 22, and min⁡(1,2)=1\min(1, 2) = 1 for the prime 33.

Method 2: Prime Factorization
gcd⁡(48,180)=22⋅31=4⋅3=12\gcd(48, 180) = 2^2 \cdot 3^1 = 4 \cdot 3 = 12
Prime factorizations — gcd(48, 180) Prime factorizations — gcd(48, 180) 48 2⁴ · 3 2 2 2 2 2 3 3 5 180 2² · 3² · 5 2 2 2 3 3 3 5 5 GCD takes the minimum exponent of each shared prime: gcd(48, 180) = 22 · 3 = 12 gcd(48, 180) = 1248 = 2⁴ · 3180 = 2² · 3² · 5Amber: shared portion at thesmaller exponent per prime.Dashed: excess + unshared.2² · 3 = 4 · 3 = 12
Pitfall: Taking the larger exponent
Taking the larger exponent of each shared prime in 40=23⋅540 = 2^3 \cdot 5 and 60=22⋅3⋅560 = 2^2 \cdot 3 \cdot 5 gives 23⋅5=402^3 \cdot 5 = 40, which does not divide 6060. The smaller exponents give gcd⁡(40,60)=22⋅5=20\gcd(40, 60) = 2^2 \cdot 5 = 20.

Each shared prime comes with two exponents, one from each factorization, and the GCD can use only one of them. In the figure, the amber blocks of each stack mark the copies of a prime that both numbers contain, and the dashed blocks mark the copies that only one of them has.

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.
The pair of this section, one step at a time. Press Next to carry out each step.
DownloadPNG2×PDF
gcd⁡(48,180)\gcd(48, 180)Step 1 of 4
Step
gcd⁡(48,180)\gcd(48, 180)
1
Write the prime factorization of each number
48=24⋅3148 = 2^4 \cdot 3^1 and 180=22⋅32⋅51180 = 2^2 \cdot 3^2 \cdot 5^1
2
Keep the primes that appear in both
22 and 33
3
Take the smaller exponent of each shared prime
min⁡(4,2)=2\min(4, 2) = 2 and min⁡(1,2)=1\min(1, 2) = 1
4
Multiply
22⋅31=4⋅3=122^2 \cdot 3^1 = 4 \cdot 3 = 12
The method on one pairLearn Math Class

Method 3: Euclidean Algorithm

Fact: Fibonacci neighbours are the slowest pairs
Run on 8989 and 5555, the algorithm walks down the Fibonacci numbers 34,21,13,…,134, 21, 13, \ldots, 1 and takes 99 divisions, more than any pair whose smaller number is below 5555. Lamé proved in 1844 that consecutive Fibonacci numbers are the slowest pairs of their size, which caps the count at five divisions per digit of the smaller number.

The Euclidean algorithm computes the GCD without factoring either number. It relies on a single property: gcd⁡(a,b)=gcd⁡(b,  a mod b)\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.

Example
For gcd⁡(252,105)\gcd(252, 105):
252=105⋅2+42252 = 105 \cdot 2 + 42, so gcd⁡(252,105)=gcd⁡(105,42)\gcd(252, 105) = \gcd(105, 42).
105=42⋅2+21105 = 42 \cdot 2 + 21, so gcd⁡(105,42)=gcd⁡(42,21)\gcd(105, 42) = \gcd(42, 21).
42=21⋅2+042 = 21 \cdot 2 + 0, so gcd⁡(42,21)=21\gcd(42, 21) = 21.
The last nonzero remainder is 2121, which is gcd⁡(252,105)\gcd(252, 105).
Euclidean algorithm chainEuclidean algorithm — gcd(252, 105)252=105· 2+42105=42· 2+2142=21· 2+0stopgcd = 21gcd(252, 105) = 21Replace (a, b) with (b, a mod b)until the remainder reaches 0.The last nonzero remainderis the GCD — here, 21.
Pitfall: Keeping the larger number
Dividing 252252 by the remainder 4242 gives 252=42⋅6+0252 = 42 \cdot 6 + 0 and the answer 4242, which does not divide 105105. The remainder divides 105105: 105=42⋅2+21105 = 42 \cdot 2 + 21, so the GCD is 2121.

The algorithm works because any common divisor of aa and bb is also a common divisor of bb and a mod ba \bmod b. The modulo operation peels away multiples of bb from aa, 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.
252 = 105 · 2 + 42105 = 42 · 2 + 2142 = 21 · 2 + 0stopgcd = 21
gcd(252, 105) = 21 in three divisions

Each line replaces the pair (a, b) by (b, a mod b): the remainder 42 becomes the new divisor, then 21, and when the remainder reaches 0 the divisor standing there, 21, is the answer. Three divisions did the work that factoring 252 and 105 would have taken much longer to do. Watch the pairs shrink for any two numbers on the Euclidean algorithm visualizer.

The next section writes the same steps out as a procedure to follow by hand.
Replacing a pair by the smaller number and the remainder never changes the GCD, so division alone finds it, with no factoring.

Euclidean Algorithm Step by Step

The procedure is mechanical. Start with two positive integers aa and bb, with a≥ba \geq b.

Compute r=a mod br = a \bmod b. Replace aa with bb and bb with rr. Repeat until b=0b = 0. The value of aa at that point is the GCD.

Example
For gcd⁡(462,198)\gcd(462, 198):
462=198⋅2+66→a=198,  b=66462 = 198 \cdot 2 + 66 \quad \to \quad a = 198, \; b = 66
198=66⋅3+0→b=0198 = 66 \cdot 3 + 0 \quad \to \quad b = 0
gcd⁡(462,198)=66\gcd(462, 198) = 66.
Euclidean algorithm chainEuclidean algorithm — gcd(462, 198)462=198· 2+66198=66· 3+0stopgcd = 66gcd(462, 198) = 66Each step replaces the largernumber by the remainder.Terminates in two steps —66 divides 198 exactly.
Example
For gcd⁡(1,071,462)\gcd(1{,}071, 462):
1071=462⋅2+147→a=462,  b=1471071 = 462 \cdot 2 + 147 \quad \to \quad a = 462, \; b = 147
462=147⋅3+21→a=147,  b=21462 = 147 \cdot 3 + 21 \quad \to \quad a = 147, \; b = 21
147=21⋅7+0→b=0147 = 21 \cdot 7 + 0 \quad \to \quad b = 0
gcd⁡(1071,462)=21\gcd(1071, 462) = 21.
Euclidean algorithm chainEuclidean algorithm — gcd(1071, 462)1071=462· 2+147462=147· 3+21147=21· 7+0stopgcd = 21gcd(1071, 462) = 21Three steps, larger inputs.Same termination condition:remainder reaches 0.
The algorithm always terminates because the remainder rr satisfies 0≤r<b0 \leq r < b, so bb strictly decreases at each step. A sequence of positive integers that strictly decreases must eventually reach zero.
The same procedure with its loop marked. Press Next to carry out one step at a time and watch bb fall to 00.
DownloadPNG2×PDF
gcd⁡(1071,462)\gcd(1071, 462)Step 1 of 11
Values now
aa =10711071bb =462462rr =–
This step
Take a=1071a = 1071 and b=462b = 462. The larger number is aa.
Algorithm
1Start with two positive integers aa and bb, with a≥ba \geq b
2Compute r=a mod br = a \bmod b
3Replace aa with bb and bb with rr
4Repeat until b=0b = 0
5The value of aa at that point is the GCD
Passes finished so far
a=b⋅q+ra = b \cdot q + rnew aanew bb
11071=462⋅2+1471071 = 462 \cdot 2 + 147462462147147
2462=147⋅3+21462 = 147 \cdot 3 + 211471472121
3147=21⋅7+0147 = 21 \cdot 7 + 0212100
Result
The Euclidean algorithm as a loop·/arithmetic/divisibility/gcdLearn Math Class

Coprime (Relatively Prime) Numbers

Two numbers are coprime — also called relatively prime — when their GCD is 11. They share no common factor except the trivial one.

The numbers 88 and 1515 are coprime: the factors of 88 are {1,2,4,8}\{1, 2, 4, 8\}, the factors of 1515 are {1,3,5,15}\{1, 3, 5, 15\}, and the only overlap is 11.

The numbers 99 and 1212 are not coprime: gcd⁡(9,12)=3\gcd(9, 12) = 3.

The numbers 77 and 2020 are coprime: 77 is prime and does not divide 2020.

Two structural facts generate coprime pairs reliably.

THEOREM
Any two consecutive integers are coprime — gcd⁡(n,n+1)=1\gcd(n, n+1) = 1 for all nn — because any common divisor of nn and n+1n+1 would have to divide their difference, which is 11.

And a prime pp is coprime with every number it does not divide.
Common factors of two numbersfactors of 81248factors of 1513515gcd(8, 15) = 1largest common factorfactors of 8 and 15only 1 is sharedgcd(8, 15) = 1coprime, yet neithernumber is prime
Coprime without being prime

The factors of 8 are 1, 2, 4, 8; the factors of 15 are 1, 3, 5, 15. The only chip the two rows share is 1, so gcd(8, 15) = 1 and the numbers are coprime. Neither 8 nor 15 is prime: coprimality is about the pair having no common factor, not about either number on its own.

Compare 9 and 12, whose rows share 1 and 3: gcd = 3, not coprime.

Properties of Coprime Numbers

Coprimality enables conclusions that fail for numbers with shared factors.

Fact: Coprime coins pay every large amount
Coins worth 33 and 55 pay every whole amount from 88 on, since 88, 99 and 1010 can be paid and adding coins of 33 reaches the rest; 77 is the largest amount they miss. Coins worth 44 and 66 share the factor 22, so no number of them ever pays an odd amount.

If gcd⁡(a,b)=1\gcd(a, b) = 1 and a∣(b⋅c)a \mid (b \cdot c), then a∣ca \mid c. When aa and bb share no common factor, the factor aa hiding inside the product b⋅cb \cdot c must come entirely from cc. Without coprimality, this inference breaks — 6∣(4⋅3)6 \mid (4 \cdot 3) does not imply 6∣36 \mid 3.

If gcd⁡(a,b)=1\gcd(a, b) = 1 and gcd⁡(a,c)=1\gcd(a, c) = 1, then gcd⁡(a,b⋅c)=1\gcd(a, b \cdot c) = 1. Coprimality with individual factors extends to their product.

If gcd⁡(a,b)=1\gcd(a, b) = 1, then gcd⁡(a2,b2)=1\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 66 can be tested by checking 22 and 33 separately works precisely because gcd⁡(2,3)=1\gcd(2, 3) = 1. Coprimality is what makes the combined divisibility rules valid.
DownloadPNG2×PDF
Layout
PropertyStatementExample
Euclid's lemmaif gcd(a, b) = 1 and a ∣ (b · c), then a ∣ cgcd(7, 15) = 1 and 7 ∣ (15 · 21 = 315), so 7 ∣ 21 ✓
Coprimality with a productif gcd(a, b) = 1 and gcd(a, c) = 1, then gcd(a, b · c) = 1gcd(5, 4) = 1 and gcd(5, 9) = 1, so gcd(5, 36) = 1 ✓
Coprimality under powersif gcd(a, b) = 1, then gcd(aⁿ, bⁿ) = 1 for every n ≥ 1gcd(8, 15) = 1, so gcd(64, 225) = 1 ✓
Properties of Coprime NumbersLearn Math Class

GCD of More Than Two Numbers

The GCD extends to any number of inputs by applying it pairwise. The key identity is:

GCD of More Than Two Numbers
gcd⁡(a,b,c)=gcd⁡(gcd⁡(a,b),  c)\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.

Example
For gcd⁡(24,36,60)\gcd(24, 36, 60):
gcd⁡(24,36)=12\gcd(24, 36) = 12.
gcd⁡(12,60)=12\gcd(12, 60) = 12.
So gcd⁡(24,36,60)=12\gcd(24, 36, 60) = 12.

Example
For gcd⁡(18,30,42)\gcd(18, 30, 42):
gcd⁡(18,30)=6\gcd(18, 30) = 6.
gcd⁡(6,42)=6\gcd(6, 42) = 6.
So gcd⁡(18,30,42)=6\gcd(18, 30, 42) = 6.

RULE
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 2436\frac{24}{36} reduces to 23\frac{2}{3} by dividing numerator and denominator by gcd⁡(24,36)=12\gcd(24, 36) = 12. A fraction is in lowest terms when the GCD of its numerator and denominator is 11.

Pitfall: Stopping at a smaller common factor
Dividing 1824\frac{18}{24} by the common factor 22 and stopping gives 912\frac{9}{12}, which is not in lowest terms: 99 and 1212 still share 33. Dividing by gcd⁡(18,24)=6\gcd(18, 24) = 6 gives 34\frac{3}{4} at once.

Any common factor of the numerator and denominator can be cancelled, and every cancellation gives a fraction of the same value. What differs is how far a single cancellation goes: the larger the common factor, the smaller the numbers that remain.

Ratios simplify the same way. A rectangle with dimensions 48×8048 \times 80 has an aspect ratio of 48:8048:80. Dividing both by gcd⁡(48,80)=16\gcd(48, 80) = 16 gives 3:53:5, as the figure below shows.
48 × 80 rectangleAspect ratio 48:80 reduced by gcd(48,80)=16 to 3:5.354880aspect ratio 48 : 80divide both by gcd(48, 80) = 1648 / 16 = 380 / 16 = 548 : 80 = 3 : 53 and 5 are coprime — lowest terms
Tiling problems use the GCD geometrically.

Example
The largest square tile that fits perfectly into a 48×8048 \times 80 rectangle has side length gcd⁡(48,80)=16\gcd(48, 80) = 16. The rectangle is then covered by 3×5=153 \times 5 = 15 such tiles with no gaps or overlaps, as shown below.
48 × 80 rectangleLargest square tile of side gcd(48,80)=16; 3 × 5 = 15 tiles cover the rectangle exactly.164880largest square tileside = gcd(48, 80) = 1648 / 16 = 3 tiles across80 / 16 = 5 tiles down3 × 5 = 15 tilesno gaps, no overlaps
The GCD also connects to the LCM through a clean identity: a⋅b=gcd⁡(a,b)⋅lcm(a,b)a \cdot b = \gcd(a, b) \cdot \text{lcm}(a, b). Knowing the GCD gives the LCM for free, and vice versa.
Reducing fractions, simplifying ratios and tiling rectangles ask one question: the largest number that divides both quantities.

Worked Examples

Find gcd⁡(56,84)\gcd(56, 84) by listing factors. Factors of 5656: {1,2,4,7,8,14,28,56}\{1, 2, 4, 7, 8, 14, 28, 56\}. Factors of 8484: {1,2,3,4,6,7,12,14,21,28,42,84}\{1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84\}. Common: {1,2,4,7,14,28}\{1, 2, 4, 7, 14, 28\}. GCD =28= 28.

Find gcd⁡(120,84)\gcd(120, 84) by prime factorization. 120=23⋅3⋅5120 = 2^3 \cdot 3 \cdot 5 and 84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7. Shared primes: 2min⁡(3,2)⋅3min⁡(1,1)=22⋅3=122^{\min(3,2)} \cdot 3^{\min(1,1)} = 2^2 \cdot 3 = 12.

Find gcd⁡(782,253)\gcd(782, 253) by the Euclidean algorithm. 782=253⋅3+23782 = 253 \cdot 3 + 23. Then 253=23⋅11+0253 = 23 \cdot 11 + 0. GCD =23= 23.

Are 3535 and 5454 coprime? gcd⁡(35,54)\gcd(35, 54): 54=35⋅1+1954 = 35 \cdot 1 + 19, 35=19⋅1+1635 = 19 \cdot 1 + 16, 19=16⋅1+319 = 16 \cdot 1 + 3, 16=3⋅5+116 = 3 \cdot 5 + 1, 3=1⋅3+03 = 1 \cdot 3 + 0. GCD =1= 1. Yes, coprime.

Simplify 84126\frac{84}{126}. gcd⁡(84,126)\gcd(84, 126): 126=84⋅1+42126 = 84 \cdot 1 + 42, 84=42⋅2+084 = 42 \cdot 2 + 0. GCD =42= 42. The fraction reduces to 23\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.
DownloadPNG2×PDF
Layout
MethodBest forHow it worksWorked example
Listing factorssmall inputs; transparent for teachinglist all factors of each number, intersect the lists, take the largestgcd(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 factorizationfactorizations are easy to obtain or already knownfactor both numbers; for each prime, take the minimum exponent appearing in either factorizationgcd(48, 180): 48 = 2⁴ · 3, 180 = 2² · 3² · 5 → 2² · 3 = 12
Euclidean algorithmlarge numbers; factorization difficult; most efficient overallrepeatedly replace (a, b) with (b, a mod b) — using the modulo operation — until b = 0; the final nonzero a is the gcdgcd(252, 105): 252 = 105·2 + 42, 105 = 42·2 + 21, 42 = 21·2 + 0 → 21
Summary: Three Methods for GCDLearn Math Class
DownloadPNG2×PDF
Before you read
Three ways to find a GCD
All three methods give the same greatest common divisor. They differ in how well they scale to large numbers.
Greatest common divisor3 methods
Listing factors
Howlist both sets of factors and intersect
Best forsmall inputs
Prime factorization
Howtake each shared prime to its minimum exponent
Euclidean algorithm
How(a,b)→(b, a mod b)(a, b) \to (b,\ a \bmod b) until the remainder is 00
Best forlarge numbers
Takeaway
Large numbers want Euclid
Listing and factorization are fine for small inputs; the Euclidean algorithm stays fast however large the numbers get.
Three methods for the GCD·/arithmetic/divisibility/gcdLearn Math Class

Formula Summary

This summary collects the rules for the greatest common divisor that the page states, one card each. Every card gives the name of the rule and its formula, a line on why it holds with a link to its section and, where the page works one through, an example; a badge marks the cards that need coprime numbers.

The first five cards are the basic properties for positive integers: a number with itself, with one and with zero, the order of the two inputs, and the bound by the smaller number. Then come the step behind the Euclidean algorithm, the rule for consecutive integers, three consequences of being coprime, and the rule that extends the GCD to three or more numbers.
DownloadPNG2×PDF
Same number
gcd⁡(a,a)=a\gcd(a, a) = a
The largest number that divides aa and aa is aa itself, from the basic properties.
With one
gcd⁡(a,1)=1\gcd(a, 1) = 1
The only positive divisor of 11 is 11, so it is the only common divisor, as the basic properties note.
With zero
gcd⁡(a,0)=a\gcd(a, 0) = a
Every positive integer divides 00, so the common divisors are just the divisors of aa (basic properties).
Order
gcd⁡(a,b)=gcd⁡(b,a)\gcd(a, b) = \gcd(b, a)
The common factors are the same in either order, one of the basic properties.
Upper bound
gcd⁡(a,b)≤min⁡(a,b)\gcd(a, b) \leq \min(a, b)
No common divisor can be larger than the smaller number, the last of the basic properties.
Euclidean step
gcd⁡(a,b)=gcd⁡(b,  a mod b)\gcd(a, b) = \gcd(b, \; a \bmod b)
Replacing the larger number by the remainder keeps the GCD and shrinks the numbers; the Euclidean algorithm repeats it until the remainder is 00.
gcd⁡(252,105)=gcd⁡(105,42)\gcd(252, 105) = \gcd(105, 42)
Consecutive integers
gcd⁡(n,n+1)=1\gcd(n, n + 1) = 1
Any common divisor of nn and n+1n + 1 divides their difference, which is 11, as coprime numbers shows.
Coprime factor
if a∣(b⋅c)a \mid (b \cdot c), then a∣ca \mid c
The factor aa inside the product must come from cc; without coprimality it fails, since 6∣(4⋅3)6 \mid (4 \cdot 3) but 6∤36 \nmid 3 (properties of coprime numbers).
!gcd⁡(a,b)=1\gcd(a, b) = 1
Coprime product
gcd⁡(a,b⋅c)=1\gcd(a, b \cdot c) = 1
Being coprime with each factor carries over to the product, from properties of coprime numbers.
!gcd⁡(a,b)=1\gcd(a, b) = 1 and gcd⁡(a,c)=1\gcd(a, c) = 1
Coprime squares
gcd⁡(a2,b2)=1\gcd(a^2, b^2) = 1
Squaring both numbers brings in no new shared primes, as properties of coprime numbers notes.
!gcd⁡(a,b)=1\gcd(a, b) = 1
More than two numbers
gcd⁡(a,b,c)=gcd⁡(gcd⁡(a,b),  c)\gcd(a, b, c) = \gcd(\gcd(a, b), \; c)
Take the GCD of the first two, then of that result with the next number, in any order; see GCD of more than two numbers.
gcd⁡(24,36,60)=gcd⁡(12,60)=12\gcd(24, 36, 60) = \gcd(12, 60) = 12
GCD rulesLearn Math Class
The Euclidean step does the computing and the other rules do the checking: a GCD larger than the smaller input, or a common divisor above one for consecutive integers, points to a slip. The coprime cards say when a factor may be cancelled safely.

Common Pitfalls

Five mistakes account for many of the wrong answers in GCD work. Four are marked where they happen in the sections above; the confusion of coprime with prime is the one the notation and coprime sections already point out. Here each is worked through in full, with the wrong and the right working side by side.
DownloadPNG2×PDF
1Confusing the GCD with the LCM
The greatest common divisor is answered with a common multiple, usually the least common multiple or the product of the two numbers. Both names contain "common", and both are found from the same two numbers.
Wrong turn
Error here
1212 and 1818 both go into 3636, so gcd⁡(12,18)=36\gcd(12, 18) = 36.
Right path
The GCD must divide both numbers. The factors of 1212 are {1,2,3,4,6,12}\{1, 2, 3, 4, 6, 12\} and the factors of 1818 are {1,2,3,6,9,18}\{1, 2, 3, 6, 9, 18\}. The common factors are {1,2,3,6}\{1, 2, 3, 6\}, so gcd⁡(12,18)=6\gcd(12, 18) = 6. The number 3636 is lcm(12,18)\text{lcm}(12, 18).
Why it happens"greatest" suggests a large answer, and "common" is read as a number both lead to rather than a number that goes into both.
How to checkThe GCD can never exceed the smaller number, so gcd⁡(12,18)≤12\gcd(12, 18) \leq 12. Both divisions must also come out whole: 12÷6=212 \div 6 = 2 and 18÷6=318 \div 6 = 3.
2Taking the larger exponent
In the prime factorization method, each shared prime is raised to the larger of its two exponents. That is the rule for the least common multiple, not for the GCD.
Start
40=23⋅540 = 2^3 \cdot 5 and 60=22⋅3⋅560 = 2^2 \cdot 3 \cdot 5.
Wrong turn
Error here
The larger exponents give 23⋅5=402^3 \cdot 5 = 40.
Right path
Take the smaller exponent of each shared prime, min⁡(3,2)=2\min(3, 2) = 2 for the prime 22 and min⁡(1,1)=1\min(1, 1) = 1 for the prime 55. The prime 33 is not shared. So gcd⁡(40,60)=22⋅5=20\gcd(40, 60) = 2^2 \cdot 5 = 20, and indeed 40=20⋅240 = 20 \cdot 2 and 60=20⋅360 = 20 \cdot 3.
Why it happensThe GCD and the LCM are read from the same two factorizations and differ only in minimum against maximum, and the word "greatest" pulls toward the larger exponent.
How to checkDivide both numbers by the result. 60÷40=1.560 \div 40 = 1.5 is not whole, so 4040 is not a common divisor at all.
3Keeping the larger number
After the first division of the Euclidean algorithm, the next division keeps the original larger number and divides it by the remainder, instead of dividing the previous divisor.
Start
For gcd⁡(252,105)\gcd(252, 105), 252=105⋅2+42252 = 105 \cdot 2 + 42,
Wrong turn
Error here
Then 252=42⋅6+0252 = 42 \cdot 6 + 0, so the GCD is 4242.
Right path
The pair moves along, (252,105)→(105,42)→(42,21)(252, 105) \to (105, 42) \to (42, 21). The steps are 105=42⋅2+21105 = 42 \cdot 2 + 21 and 42=21⋅2+042 = 21 \cdot 2 + 0, so gcd⁡(252,105)=21\gcd(252, 105) = 21.
Why it happensThe larger number feels like the number being worked on, while the rule (a,b)→(b,  a mod b)(a, b) \to (b, \; a \bmod b) drops it after the first step.
How to checkThe result must divide both original numbers. 105÷42=2.5105 \div 42 = 2.5, so 4242 fails; 252÷21=12252 \div 21 = 12 and 105÷21=5105 \div 21 = 5.
4Taking coprime to mean prime
"Relatively prime" is read as a property of each number on its own, so a pair is called coprime only when both numbers are prime.
Wrong turn
Error here
Neither 88 nor 1515 is prime, so 88 and 1515 are not coprime.
Right path
The factors of 88 are {1,2,4,8}\{1, 2, 4, 8\} and the factors of 1515 are {1,3,5,15}\{1, 3, 5, 15\}. The only common factor is 11, so gcd⁡(8,15)=1\gcd(8, 15) = 1 and the two numbers are coprime.
Why it happensThe word "prime" inside "relatively prime" suggests that the numbers themselves must be prime.
How to checkCompute the GCD. Two numbers are coprime exactly when their GCD is 11, whether or not either of them is prime.
5Stopping at a smaller common factor
A fraction is divided by a common factor that is not the greatest one, and the result is taken to be in lowest terms.
Wrong turn
Error here
1818 and 2424 are both even, so 1824=912\frac{18}{24} = \frac{9}{12}, and the fraction is simplified.
Right path
99 and 1212 still share the factor 33, so 912=34\frac{9}{12} = \frac{3}{4}. In one step, gcd⁡(18,24)=6\gcd(18, 24) = 6 and 18÷624÷6=34\frac{18 \div 6}{24 \div 6} = \frac{3}{4}.
Why it happensThe first common factor that is spotted, often 22, is cancelled, the result looks simpler, and the check that nothing else is shared is skipped.
How to checkFind the GCD of the new numerator and denominator. gcd⁡(9,12)=3\gcd(9, 12) = 3 means the fraction is not finished; gcd⁡(3,4)=1\gcd(3, 4) = 1 means it is.
Common pitfalls with the GCD·/arithmetic/divisibility/gcdLearn Math Class
Each slip loses the condition that the GCD divides both numbers. It is never larger than the smaller number, it takes the smaller exponent of each shared prime, the Euclidean algorithm carries the divisor and the remainder forward, coprime means a GCD of 11 whether or not the numbers are prime, and a fraction is in lowest terms only when its new numerator and denominator have GCD 11. Dividing both numbers by the answer catches each slip.

Skills You Should Learn

Each skill opens its step-by-step method page. Skills marked "On this page" are taught above.
Taught on this page
More arithmetic methods
  • Simplify fractionsReduce a fraction to lowest terms: divide the numerator and the denominator by their GCD, as in 84126=23\frac{84}{126} = \frac{2}{3}.
  • Find the least common multipleFind the smallest number that two or more numbers divide: take every prime with its larger exponent, or use lcm⁡(a,b)=a⋅bgcd⁡(a,b)\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}.

GCD FAQ

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

+
They are the same concept under different names. GCD (greatest common divisor) is the standard term in mathematics; HCF (highest common factor) is the usual British and Indian schoolbook name; GCF (greatest common factor) appears in American textbooks. All three label the same number — the largest integer dividing both inputs. Compute it with the GCF calculator.Read more →

Why are coprime numbers important?

+
Coprimality unlocks key divisibility reasoning. 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 — gcd(2, 3) = 1 — and why a fraction is fully simplified exactly when its numerator and denominator are coprime. Any two consecutive integers are coprime, a fact many proofs exploit.Read more →

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. Dividing by the GCD reaches lowest terms in one step, where cancelling small common factors one at a time may take several rounds. A fraction is fully reduced exactly when gcd(numerator, denominator) = 1.Read more →

What is gcd(a, 0)?

+
gcd(a, 0) = a for any positive integer a. Every positive integer divides 0, so the common divisors of a and 0 are exactly the divisors of a, and the largest is a itself. This identity is what ends the Euclidean algorithm: when the remainder finally reaches zero, the other number is the answer.Read more →

Which numbers make the Euclidean algorithm take the most steps?

+
Consecutive Fibonacci numbers. On 8989 and 5555 every division but the last has quotient 11, so the remainders walk down the Fibonacci numbers 34,21,13,…,134, 21, 13, \ldots, 1 and the algorithm needs 99 divisions, more than any pair whose smaller number is below 5555. Lamé proved in 1844 that these are the slowest pairs of their size, which caps the count at five divisions per digit of the smaller number.Read more →

What is the largest amount coins of 3 and 5 cannot pay?

+
77. Coins worth 33 and 55 pay 8=3+58 = 3 + 5, 9=3+3+39 = 3 + 3 + 3 and 10=5+510 = 5 + 5, and adding coins of 33 to these reaches every larger amount; the only amounts missed are 11, 22, 44 and 77. This works because gcd⁡(3,5)=1\gcd(3, 5) = 1: for coprime values aa and bb the largest missed amount is ab−a−bab - a - b, here 15−3−5=715 - 3 - 5 = 7. Coins of 44 and 66 share the factor 22, so they never pay an odd amount.Read more →

Can two numbers be coprime if neither is prime?

+
Yes. Coprime describes a pair, not either number on its own: two numbers are coprime when their GCD is 11. Neither 8=238 = 2^3 nor 15=3⋅515 = 3 \cdot 5 is prime, yet they have no prime factor in common, so gcd⁡(8,15)=1\gcd(8, 15) = 1. Nor is one prime in the pair enough: 77 and 1414 share the factor 77. The test is always the GCD, never the primality of either number.Read more →