I’ll close this series on prime numbers by looking at how to find the prime factorization of a number, starting with the most basic ideas applicable to relatively small numbers, and then (next week) looking at some advanced methods for larger numbers.

## What is a prime factorization?

We’ll start with this question from 1997:

Prime Factorization The other day while I was gone, my class learned about prime factors. Now we have a homework sheet that says "Write the prime factorization for each number". I don't know what it means. Could you please help me?

Doctor Wallace answered first:

Hi Jayme! Let's begin with some definitions. Afactoris an integer that exactly divides a given integer. For example, if we are given the number 12, we can list its factors as the following: 1, 2, 3, 4, 6, and 12. This is because each of these numbers goes into 12 evenly, with no remainder. Notice that 5, for example, is not listed, because 12 divided by 5 leaves a remainder. Now, aprime numberis one that has only 2 factors: 1 and itself. For example, 7 is a prime number, because if we list out all its factors, we only have 1 and 7 on the list. No other number divides into 7 without leaving a remainder.

Those are the words; what about the phrase?

Now, we can combine these two ideas and ask about theprime factors of a number. For example, what are the prime factors of 12? Answer: 2 and 3. (We can also include 1, but since it is a factor of every number, it is usually omitted from such lists.) These are the only two prime numbers in the list of the factors of 12, so they are 12's prime factors.

We see here why 1 is not considered as a prime, even though it once was. It just complicates things that are already complicated enough!

Now for your homework. It asks you to write the "prime factorization" of a number. That's just a little different from writing a number's prime factors. It's important that you understand this. We listed 2 and 3 as the prime factors of 12, but they are NOT the prime factorization of 12. The two ideas are different.

Prime factors are just a list; we want something more.

So what isprime factorization? Well, there is a theorem in mathematics that says that any integer can beexpressed as the product of its prime factors. This means that we can write a number using only the product of its prime factors, and we areallowed to repeat some of themif we need to. Let's look at an example. Let's take our friend12. We've already seen that theprime factors of 12 are 2 and 3. So how can we write 12 as a product of these factors? Well, 2 x 3 = 6. If we multiply 6 by 2, we'll get 12. So12 can be written as 2 x 2 x 3. This is called the prime factorization of 12. (The numbers could be written in any order, but usually we write the smaller ones first, and then go to the bigger.)

Putting the smaller prime factors first is not *required*, but is a common *preference*; this way, there is only one way to write it, making it easier for teachers to check! We could also write it using exponents:

$$12=2\times2\times3=2^2\times3$$

### Primes-first approach

Let's do another one. How about10? The prime factors of 10 are 2 and 5. Since 2 x 5 = 10, the prime factorization of 10 is 2 x 5.

$$10=2\times5$$

I don't know what kinds of numbers are on your homework sheet. If they aresmall numbers, like these in my examples, you should be able to figure them out without too much trouble. Just remember that in the prime factorization, you can only use prime numbers, and they must be factors of the number you're trying to find the prime factorization for. You may use any of the number's prime factors as many times as you like. And you know what else?Each number has only one prime factorization. Finding it is a little like a puzzle.

This is called the **Fundamental Theorem of Arithmetic**, or the **Unique Factorization Theorem**. (It really applies only to all integers *greater than 1*, since 1 is not a prime.)

Suppose you havelarger numbers. For example, how would you find the prime factorization of126? Well, one way you could start would be by noticing that 126 is even. 2 is the only even prime number, and it divides evenly into every even number. So, if we divide 126 by 2 we get 63. We know from our multiplication tables that 63 = 9 x 7. We know that 7 is prime; what about 9? Nine is not prime: 9 = 3 x 3. So now we can stop since we have reached only prime numbers. So the prime factorization of 126 is: 126 = 2 x 3 x 3 x 7 = 2 x 9 x 7 = 2 x 63 = 126

We found one prime factor at a time, first the 2, then the 7, then the 3’s: $$126=2\times3^2\times7.$$ We’ll see more examples as we go.

I hope that makes it easier to see. If you start with an odd number, you canguess what might go into it, until you find a factor. Try prime numbers, of course, like 3, 5, 7, 11, and 13. When you find one that works, then divide it into your number, andrepeat the process with the new, smaller numberyou get, just as we did above.

### Factors-first approach

Then Doctor Mitteldorf joined in, four days later, with a slightly different perspective:

Dear Jayme, When youfactor a number, you're justfinding some numbersthat can be multiplied together to make that number. You can factor 24 by saying 6*4 or you could just as well say 12*2 or 8*3.Prime factorizationis when youfinish the processby breaking down each of your factor numbers, and keep going until you get to numbers that aren't divisible by any others (except, of course, 1 or the number itself).

This is a different approach than Doctor Wallace’s one-prime-at-a-time style; as we’ll see later, this can be expressed as a “tree”. We break the number into parts, and then break each of those into smaller parts, until we can’t go any further.

For example, if you said24 was 6*4, you might change the 6 to 3*2 and the 4 to 2*2, and you'd have 24 = 3*2*2*2. If you said24 was 8*3, you'd break down the 8 into 2*2*2, and you'd end up with the same thing as before: 24 = 3*2*2*2. (The order of the numbers doesn't matter.)

We’ll see this drawn as a tree below.

## How to do it (small numbers)

A 1996 question focuses on the process:

Write Numbers as Products of Prime Factors I need to write 4, 6, 8, 10, 12, and 14 asproducts of their prime factors. Please help! My mind is a blank.

Doctor Jaime answered, using one of these as an example, and then a slightly larger one:

Recall thatprime numbersare divisible only by themselves and one. Examples are: 2, 3, 5, 7, 11, 13, etc. The prime factors you need are prime numbers such that their product is the given number. So you need to do two things: 1.find the prime numbersthat are factors of the given number; 2. write the given number as aproduct of the prime factorsfound. To obtain the prime factors you just have todivide the given number by the prime numbersand see which divide the given number (with zero remainder). You begin by using the smaller prime numbers, because they are easier, to see which ones divide your number. When you find a prime number that divides your number, you get a certain quotient and you thenbegin the same process with the quotient.

### Factoring 12

For example, let's try this with number12. We begin with the smallest prime number: 2. 12 divided by 2 gives 6 as a quotient and zero as a remainder. So 2 divides 12, and we can say that12 = 2 x 6. We have now written 12 as a product of two numbers, 2 and 6, but they are not both prime factors. 2 is a prime number, but 6 is not. Therefore, we now need to write 6 as a product of prime factors.Again we begin with the smallest prime number: 2. 6 divided by 2 gives 3 as a quotient and zero as a remainder. So 2 divides 6, and we can say that6 = 2 x 3. The divisions end here because the quotient obtained, 3, is a prime number (it can only be divided by itself and give quotient 1). Now, how do we write 12 as a product of its prime factors (2 and 3 in this case)? Above we have obtained 12 = 2 x 6 = 2(2 x 3) = 2^2 x 3, (where 2^2 means 2 squared or 2 raised to the second power). So it must be:12 = 2^2 x 3

We just pulled out one prime at a time, and put them together to show the product; we can do this as a stack of divisions:

$$\begin{array}{rrr}{3}\\2\overline{\big)6}\\2\overline{\big)12}\end{array}$$ $$12=2^2\times3$$

### Factoring 45

Let's try again with number45, for example. We begin with the smallest prime number: 2. 45 divided by 2 doesnotgive zero as a remainder, so we must move to the next prime number, 3. 45 divided by 3 gives 15 as a quotient and zero as a remainder, so 3 divides 45, and we can say that45 = 3 x 15. 15 divided by 3 gives 5 as a quotient and zero as a remainder. So 3 divides 15, and we can say that15 = 3 x 5. The divisions end here because the quotient obtained, 5, is a prime number. So 3 and 5 are the only prime factors of 45. Now, how do we write 45 as a product of its prime factors (3 and 5 in this case)? Above we have obtained 45 = 3 x 15 = 3 * (3*5) = 3^2 * 5. So it must be:45 = 3^2 * 5You can again verify that it is really so, doing the calculation.

$$\begin{array}{rrr}{5}\\3\overline{\big)15}\\3\overline{\big)45}\end{array}$$ $$45=3^2\times5$$

### Making a factor tree for 24

Another method to find the prime factors is to use the so-called "factor trees." Youfind factorsof your number, and thenfactors of these factors, etc., until you arrive at prime numbers. For example, if you want to factor24, you may know that 24 = 6 x 4. But 6 = 2 x 3 and 4 = 2 x 2, and all the factors are prime. You can write this as a "tree": 24 / \ 6 4 / \ / \ 2 3 2 2 So the prime factors are 2 and 3. But 2 shows up three times and 3 shows up once, so: 24 = 2^3 x 3

I describe this approach as “opportunistic”: we happen to see a product, whether it involves a prime or not, and continue from there. The “leaves” of the tree (at the ends) are the primes.

As Doctor Mitteldorf mentioned above, we could also have done this with a different starting point:

24 / \ 8 3 / \ 2 4 / \ 2 2

Again, this leads to \(24=2^3\times3\).

## Factor trees for bigger numbers

For more on that last idea, see this 1998 question:

Making a Factor Tree How do you make afactor tree? I know what one is but my teacher gave us a quiz and I didn't know how to do it.

Doctor Mike answered with a bigger example:

Dear Kelsy, There are several ways to write these things down, and I will show you one. That will give you the idea. Here's an example. Let's say you want to factor630. Because there is a zero on the endyou know it has 10 as a factor. It can be written 63 * 10. Both of these factors can be factored further.Ten is 5*2and that's all.63 is 9*7, which gives the prime 7 and also9 which is 3*3. We can show all of this in a "tree" drawing like this. 630 / \ / \ / \ 63 10 / \ / \ / \ / \ 9 7 5 2 / \ / \ 3 3

Again, he started with an “obvious” pair of factors, and continued from there.

All of the numbers at the bottom (theleaveson the tree) areprime numbers, so you are done. To write out the factorization in an equation, you multiply all of them like this:630 = 3*3*7*5*2. Sometimes teachers want them written inincreasing orderlike this:630 = 2*3*3*5*7.

Or, as we’ve seen, we can write it using exponents: $$630=2\times3^2\times5\times7$$ You should do it whichever way is recommended in your classroom, or otherwise whatever way you like!

Sometimes people write the original number 630 on the bottom and have the connecting lines go upwards, so the "leaves" will be on top. Whether you draw trees or not, the basic idea is that tofactor a number completely, you first have to start somewhere, the way I started with 630 = 63*10.You could have started differently.You could have started by noticing that 630 is even and written down 630 = 2*315. That's fine. No matter how you start, you have to keep on until everything is factored completely into primes.

The important thing is that, regardless of the order, you will get the same result.

## Pulling out bricks

Here is a 2001 question, from a student who knew only about factor trees, and didn’t like them:

Prime Factors as Bricks I have trouble with prime factorization. I need an easier way to do it than making a tree.

After a preliminary answer with a reference to divisibility rules (which help to decide whether to bother to divide by certain small numbers), I tried:

Hi, Andre. Let's try taking the most basic approach I can think of, to see what this is all about. The prime numbers are the building blocks of which any whole number can be built by multiplying them together. Think of them as bricks. Some buildings might consist of a single brick (weird, but possible); most will be built of a number of bricks. Some of those bricks might be different sizes or colors, others might be identical. Suppose we want tobreak a building down into a pile of bricks, to see what it is made of. How do we do it? One brick at a time. That's what we want to do with numbers: tobreak them down by pulling out one brick (prime factor) at a time and putting them in piles.

We are going to take a brick wall,

and turn it into a neat pile of bricks,

### Systematic method

So let's take the number245. There are two main ways to find the factors. One is to methodically go throughall the possible prime factorsand see if they are there. So we get a list of small primes to try: 2, 3, 5, 7, 11, ... Try one at a time, starting at the beginning of the list. Is there a2in this number? Divide by 2, and you find that it doesn't divide evenly. How about3? Again, it doesn't go in. (This is where knowing those divisibility rules can save time, but you can just do the divisions if you prefer not to take the time to learn them.) Now wetry 5: ___49_ 5 ) 245 It goes evenly, so we know that245 = 5 * 49We've pulled one brick out of the wall, and what's left of the wall is 49.

You may immediately recognize what sort of number 49 is; but you don’t need to. (Go ahead and use it if you do!)

Now we can see what prime factors there are in 49. We firstcheck whether there is another 5in there; taking one out doesn't mean there isn't another! (On the other hand, we knew we didn't have to try 3 again, because we know there weren't any there.) But 49 is not divisible by 5, so we continue through our list of primes. Is 49 divisible by 7? Yes, and the quotient is another 7: 49 = 7 * 7 so245 = 5 * 7 * 7Since we know 7 is a prime, we're finished; we have a pile of prime "bricks." The only thing left to do, if we want, is to pile up identical bricks by combining groups of the same prime as powers: 245 = 5 * 7^2 That's it!

Each time a division **fails**, we’ve learned something about the number that won’t change as we proceed; each time we **succeed**, we add a prime to our product, but don’t know whether there is another there until we try again.

### Opportunistic method

The other approach is the opportunistic method: rather than go through the primes in order, we oftensee an obvious prime to pick first. (That's like seeing a loose brick sticking out and pulling that one out first, rather than starting at the top.) In this case, since 245 ends with 5, we can tell immediately that it isdivisible by 5, so we would divide by that first. Then when we see 49, we should recognize that as asquare, and can just write it that way. All that comes with experience. If you just want to take the slow route and make sure you get the job done, that's fine. The important thing is that you are getting to know how numbers are built.

Sometimes, the obvious factor is *not* a prime, as if a chunk of bricks fell out of the wall, ready to break apart. That’s really all the tree method does!

Andre replied:

Thanks, that was much simpler.

The tree may be *faster*; but first you have to *understand*.

Pingback: Prime Factorization of a Number (Advanced) – The Math Doctors