Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Find the GCD by Prime Factorization

The greatest common divisor is the largest number that divides both numbers. Factor both into primes; the GCD keeps only the primes they share, each with the smaller of its two exponents.

Recognize the task

Wording such as "greatest common divisor", "greatest common factor (GCF)", "largest number that divides both", "largest square tile", or a fraction to reduce. Typical inputs: gcd⁡(36,60)\gcd(36, 60), gcd⁡(84,126,210)\gcd(84, 126, 210), numbers already given as 23⋅322^3 \cdot 3^2. Test: if you can factor both numbers in a few steps, use this method; for large numbers that resist factoring, use the Euclidean algorithm.
The GCD and the notation gcd⁡(a,b)\gcd(a, b) are defined in the GCD lesson.

Ways to do it

Prime factorizationusual
gcd⁡(a,b)=∏pmin⁡(αp,βp)\gcd(a, b) = \prod p^{\min(\alpha_p, \beta_p)}
For each prime in both numbers, take the smaller exponent.
Listing factorssmall numbers
largest number in both factor lists\text{largest number in both factor lists}
List all factors of each number and pick the largest common one (listing factors); fine for numbers below about 100100.
Euclidean algorithmlarge numbers
gcd⁡(a,b)=gcd⁡(b,  a mod b)\gcd(a, b) = \gcd(b, \; a \bmod b)
Needs no factoring; see the Euclidean algorithm method.

Steps

StepOn gcd⁡(72,120)\gcd(72, 120)
1Factor each number into primes. Use prime factorization on each number separately.72=23⋅3272 = 2^3 \cdot 3^2,   120=23⋅3⋅5\; 120 = 2^3 \cdot 3 \cdot 5
2Keep the primes that appear in both. A prime that divides only one of the numbers cannot divide the GCD.22 and 33 (not 55)
3Take the smaller exponent of each shared prime. The GCD can use only as many copies of a prime as both numbers contain.2min⁡(3,3)⋅3min⁡(2,1)=23⋅32^{\min(3, 3)} \cdot 3^{\min(2, 1)} = 2^3 \cdot 3
4Multiply. Check: the GCD divides both numbers, and the two quotients share no factor.gcd⁡(72,120)=24\gcd(72, 120) = 24 (72=24⋅372 = 24 \cdot 3, 120=24⋅5120 = 24 \cdot 5)

Worked examples

Example 1 · two numbers

shared primes
36=22⋅3236 = 2^2 \cdot 3^2,   60=22⋅3⋅5\; 60 = 2^2 \cdot 3 \cdot 5
factor both
2min⁡(2,2)⋅3min⁡(2,1)=22⋅32^{\min(2, 2)} \cdot 3^{\min(2, 1)} = 2^2 \cdot 3
smaller exponents
gcd⁡(36,60)=12\gcd(36, 60) = 12
multiply

Example 2 · no prime in common

coprime
35=5⋅735 = 5 \cdot 7,   72=23⋅32\; 72 = 2^3 \cdot 3^2
factor both
no shared prime
only 11 divides both
gcd⁡(35,72)=1\gcd(35, 72) = 1
the numbers are coprime

Example 3 · three numbers

three inputs
84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7,   126=2⋅32⋅7\; 126 = 2 \cdot 3^2 \cdot 7
factor all three
210=2⋅3⋅5⋅7210 = 2 \cdot 3 \cdot 5 \cdot 7
55 is only here
21⋅31⋅712^1 \cdot 3^1 \cdot 7^1
smallest exponent among three
gcd⁡(84,126,210)=42\gcd(84, 126, 210) = 42
multiply
Check your answer with the GCF calculator.

See it happen

Picture each number as a stack of prime blocks: 7272 is three blocks of 22 and two blocks of 33, and 120120 is three blocks of 22, one block of 33 and one block of 55. A common divisor can only be built from blocks that both stacks have. Line the stacks up prime by prime and keep the overlap: three 22s and one 33. The overlap is the largest stack that fits inside both numbers, and that is the GCD.

Common mistakes

Taking the larger exponent

✗ gcd⁡(36,60)=22⋅32=36\gcd(36, 60) = 2^2 \cdot 3^2 = 36
✓ 3636 does not divide 6060; smaller exponents give 22⋅3=122^2 \cdot 3 = 12
The larger exponents belong to the LCM.

Including a prime that only one number has

✗ gcd⁡(36,60)=22⋅3⋅5=60\gcd(36, 60) = 2^2 \cdot 3 \cdot 5 = 60
✓ the 55 is only in 6060: gcd⁡(36,60)=12\gcd(36, 60) = 12

Answering 0 when nothing is shared

✗ gcd⁡(35,72)=0\gcd(35, 72) = 0
✓ gcd⁡(35,72)=1\gcd(35, 72) = 1: the numbers are coprime