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.
| Step | On | |
|---|---|---|
| 1 | Factor each number into primes. Use prime factorization on each number separately. | , |
| 2 | Keep the primes that appear in both. A prime that divides only one of the numbers cannot divide the GCD. | and (not ) |
| 3 | Take the smaller exponent of each shared prime. The GCD can use only as many copies of a prime as both numbers contain. | |
| 4 | Multiply. Check: the GCD divides both numbers, and the two quotients share no factor. | (, ) |