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. The same reasoning works for any whole number greater than $1$: every split trades a number for smaller pieces, the pieces can never sink below $2$, so the splitting always has to stop, and it stops exactly when only primes are left.

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.

Now try building one yourself. Start $48$ as $48 = 6 \times 8$, and split each branch until every leaf is prime.

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.

This is where the prime factorization starts paying off. Regroup the primes of $360$ any way you like and you get a genuine factor pair for free: $(2 \times 3^2) \times (2^2 \times 5) = 18 \times 20$, so $360 = 18 \times 20$. Spotting that pair by guessing would take longer than reading it off the factorization. The next lesson uses this same idea to find the greatest common factor and least common multiple of two numbers.

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. The order may change, but the same primes show up the same number of times, no matter 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 special fact about primes: if a prime divides a product of two numbers, it must divide at least one of them. Take $3$ and $2 \times 6 = 12$: the $3$ shows up in the $6$. Every prime has this guarantee. A composite number need not: $4$ divides $2 \times 6 = 12$, but $4$ divides neither $2$ nor $6$.

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. Peel off the small primes first using the divisibility rules, which shrinks the number fast and keeps the arithmetic light, as in the $360$ example above. But sometimes none of the small primes fit at all, and you have to work upward.

Common mistakes