Introduction
In elementary school, the way we learn to find the greatest common divisor (GCD) and the least common multiple (LCM) is to "list out all the divisors and compare them." But once the numbers get large, that method quickly runs into a wall.
"Prime numbers are the atoms of number? What does that have to do with the GCD and the LCM?"
The one-line answer: every natural number factors into a product of prime numbers in one and only one way, and from that factorization, taking the minimum of the exponents gives the GCD, while taking the maximum gives the LCM. And since minimum + maximum = the sum of the original exponents, the identity GCD × LCM = A × B follows all on its own.
What Is a Prime Number — the Atom of Number
A prime number is a natural number greater than 1 that is divisible only by 1 and itself. 2, 3, 5, 7, 11, 13, … these are the elementary particles of number — they cannot be broken down any further.
Just as matter is built from atoms, every natural number is built from a product of prime numbers. For example:
$$12 = 2 \times 2 \times 3 = 2^2 \times 3^1$$$$18 = 2 \times 3 \times 3 = 2^1 \times 3^2$$Here 2 and 3 are the "atoms," and \(2^2 \times 3^1\) and \(2^1 \times 3^2\) correspond to the "molecular structure" of each number. How many times each prime is contained — captured by the exponents — tells you everything about that number's identity.
The Fundamental Theorem of Arithmetic — Prime Factorization Is Unique
Every natural number greater than 1 factors into a product of prime numbers in one and only one way.
This is the Fundamental Theorem of Arithmetic. The key point is that the factorization is unique.
Take 12 as an example: no matter what order you divide it in, you always end up with \(2^2 \times 3\). Whether you start with \(2 \times 6\) or with \(3 \times 4\), once you go all the way down to the prime "leaves," you are always left with the same pieces. Thanks to this uniqueness, the prime exponents become a common language for comparing two numbers.
How the GCD Comes Out of the Prime Exponents
Let's write the prime factorizations of 12 and 18 side by side.
$$12 = 2^2 \times 3^1, \qquad 18 = 2^1 \times 3^2$$The greatest common divisor (GCD) is the largest number that divides both numbers. Viewed atom by atom in primes, you can only pull out as much as both numbers have in common — that is, the minimum of each prime's exponent.
- Prime 2: 12 has \(2^2\), 18 has \(2^1\) → in common, \(2^{\min(2,1)} = 2^1\)
- Prime 3: 12 has \(3^1\), 18 has \(3^2\) → in common, \(3^{\min(1,2)} = 3^1\)
Therefore:
$$\gcd(12, 18) = 2^1 \times 3^1 = 6$$How the LCM Comes Out of the Prime Exponents
The least common multiple (LCM) is the smallest number that can hold both numbers. Since it has to be divisible by 12 and by 18 alike, it must include all of whichever prime is used more on either side. In other words, you take the maximum of each prime's exponent.
- Prime 2: you need \(2^{\max(2,1)} = 2^2\) (to accommodate the \(2^2\) in 12)
- Prime 3: you need \(3^{\max(1,2)} = 3^2\) (to accommodate the \(3^2\) in 18)
Therefore:
$$\text{lcm}(12, 18) = 2^2 \times 3^2 = 4 \times 9 = 36$$GCD × LCM = A × B — Why It Always Holds
When you look at the minimum and maximum together for each prime, one fact emerges.
| Prime | Exponent in A (12) | Exponent in B (18) | Minimum (GCD's contribution) | Maximum (LCM's contribution) | Sum |
|---|---|---|---|---|---|
| 2 | 2 | 1 | 1 | 2 | 3 |
| 3 | 1 | 2 | 1 | 2 | 3 |
For each prime, "minimum + maximum = A's exponent + B's exponent" holds. Therefore:
$$\gcd \times \text{lcm} = (2^1 \times 3^1) \times (2^2 \times 3^2) = 2^{1+2} \times 3^{1+2}$$$$A \times B = (2^2 \times 3^1) \times (2^1 \times 3^2) = 2^{2+1} \times 3^{1+2}$$The exponents in the two expressions are exactly the same, so the results are too.
$$\gcd(12, 18) \times \text{lcm}(12, 18) = 6 \times 36 = 216 = 12 \times 18$$This logic applies in exactly the same way no matter which two natural numbers you pick, so the identity always holds.
Try It Yourself
Below, pick two numbers and a block tower is drawn for each prime. The gold blocks are the part where the two towers overlap (the GCD's contribution), the blue blocks are A's contribution alone, and the green blocks are B's contribution alone. The GCD is the product of the overlapping blocks, and the LCM is the product of the taller tower at each prime. See for yourself that the golden identity holds no matter which two numbers you choose.
Closing
A prime number is not merely "a number whose only divisors are 1 and itself" — it is part of the unique set of atoms that builds up every natural number. Because the Fundamental Theorem of Arithmetic makes that factorization unique, the prime exponents become the common language of two numbers.
- Take the minimum of the exponents prime by prime and multiply → the GCD
- Take the maximum of the exponents prime by prime and multiply → the LCM
- minimum + maximum = the sum of the exponents → GCD × LCM = A × B
Now you can see why listing out divisors one by one was always a detour.
Related reading — Why Did Number Keep Expanding from the Naturals All the Way to the Complex? (the big picture of how the home of number widens, starting from the naturals ℕ where primes live) · Why Does the Logarithm Turn Multiplication into Addition? (the same pattern, where the product in prime factorization turns into addition under the logarithm)