Prime Factorization

What a prime factorization is

A prime factorization of a whole number greater than $1$ is a way of writing it as a product of prime numbers only. For example,

Every factor on the right is prime. A number like $12$ that is composite breaks into several primes. A number that is already prime, like $7$, is its own prime factorization, a product of a single prime. The point is to keep splitting until you cannot split any further, which happens exactly when every remaining factor is prime. The splitting stops there because a prime is the kind of number that has no smaller factors to break off.

This is different from just listing factors. The factors of $12$ are $1, 2, 3, 4, 6, 12$, a mixed bag of primes and composites. The prime factorization picks out only the prime building blocks and shows how many of each you multiply together to rebuild the number. It is the recipe, not the inventory.

Every number breaks down into primes

Before learning a method, settle the basic question: can every composite number really be written this way? The answer is yes.

Watch $60$ come apart. Start anywhere you like, say $60 = 6 \times 10$. Neither piece is prime, so split each one again: $6 = 2 \times 3$ and $10 = 2 \times 5$. Every piece is now prime, and $60 = 2 \times 3 \times 2 \times 5$.

Each step traded a number for pieces smaller than it, and no piece is allowed below $2$. There is only so much room between $2$ and $60$, so the splitting runs out of places to go.

Whatever number you start with, the splitting ends in a pile of primes that multiply back to it. The question left is whether two people who split the same number in two different ways could end up with two different piles.

The factor-tree method

The most common way to carry out the splitting is a factor tree (a diagram that branches a number down into its primes). Write the number at the top. Find any two factors whose product is that number (not $1$ and the number itself, but a genuine split). Then draw a branch down to each. Whenever a number is composite, split it again. Whenever a number is prime, stop that branch and circle it. The factorization is the collection of primes at the ends of the branches, the leaves of the tree.

Take $36$. One natural split is $36 = 4 \times 9$. Neither $4$ nor $9$ is prime, so each splits again: $4 = 2 \times 2$ and $9 = 3 \times 3$. Now every leaf is prime, so we are finished.

Reading the leaves from left to right gives

It does not matter which factor you write first or which branch you split first. As long as you keep going until every leaf is prime, the leaves you collect are the prime factorization.

Repeated multiplication in exponent form

When the same prime shows up more than once, writing it out in full gets clumsy. The factorization of $36$ has two $2$s and two $3$s, and a larger number can have a prime repeated many times. There is a compact shorthand: $2 \times 2$ can be written $2^2$, and $2 \times 2 \times 2$ can be written $2^3$. The small raised number, the exponent, just counts how many copies of the prime are multiplied together. It is nothing more than shorthand for repeated multiplication:

Using this, the factorization of $36$ becomes

This compact form is called prime-power form: each distinct prime written once, with an exponent telling how many times it appears. When you write a factorization, group the equal primes together and collect them into powers, and by convention list the primes from smallest to largest. You can always expand the shorthand back into a plain product whenever you want to see every factor spelled out.

Repeated division by primes

A factor tree can branch in many shapes, which is handy but a little untidy for bookkeeping. A second method keeps everything in a single column: repeated division by primes. Divide the number by the smallest prime that goes into it, then divide the quotient by the smallest prime that goes into it. Keep going until the quotient reaches $1$. The divisors you used, in order, are the prime factorization.

Run this on $360$. The smallest prime dividing it is $2$, and you keep dividing by $2$ as long as the result stays even:

Now $45$ is odd, so $2$ is finished. The smallest prime that divides $45$ is $3$:

Finally $5$ is prime and divides itself: $5 \div 5 = 1$. We have reached $1$, so we stop. The divisors, in the order we used them, were $2, 2, 2, 3, 3, 5$, so

The divisibility rules from earlier in this chapter make each step quick. They tell you at a glance whether $2$, $3$, or $5$ divides the current number, so you rarely have to guess.

The Fundamental Theorem of Arithmetic

Here is the result that makes prime factorization so powerful. We saw that $36$ could be started as $4 \times 9$. But you could just as well start it as $6 \times 6$, or as $2 \times 18$. Do those other starting splits change the final answer?

Both trees end in the same four primes: two $2$s and two $3$s. The order of the leaves changes, but the collection does not. This is not a lucky coincidence of $36$. It is a law that holds for every whole number, important enough to have a name.

Apart from the order in which you write the factors, every whole number greater than $1$ has exactly one prime factorization. That statement is the Fundamental Theorem of Arithmetic. There is one and only one multiset of primes whose product is your number. That is why the answer never depends on how you start the tree. That uniqueness is also why we can speak of the prime factorization of a number rather than a prime factorization.

Why is the answer always the same? It comes down to one thing primes do. If a prime divides a product, it divides one of the two numbers being multiplied. Take $3$ and $2 \times 6 = 12$: the $3$ shows up in the $6$. A prime has no smaller pieces, so it cannot put half of itself in each number. It goes into one or the other, whole.

That is what ties two prime lists together. Every prime in one list has to match a prime in the other, so neither list can hold anything the other is missing.

So a prime factorization is a fact about the number, not a choice you make.

Larger numbers, same method

Nothing changes for bigger numbers; you just take more steps. The trick is to peel off the small primes first using the divisibility rules, which shrinks the number fast and keeps the arithmetic light.

Common mistakes