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. A factor is 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, a prime number is 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 the prime 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 is prime factorization? Well, there is a theorem in mathematics that says that any integer can be expressed 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 are allowed to repeat some of them if we need to. Let's look at an example. Let's take our friend 12. We've already seen that the prime 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. So 12 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 about 10? 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 are small 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 have larger numbers. For example, how would you find the prime factorization of 126? 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 can guess 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, and repeat the process with the new, smaller number you 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 you factor a number, you're just finding some numbers that 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 factorization is when you finish the process by 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 said 24 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 said 24 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 as products 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 that prime numbers are 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 numbers that are factors of the given number; 2. write the given number as a product of the prime factors found. To obtain the prime factors you just have to divide the given number by the prime numbers and 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 then begin the same process with the quotient.
Factoring 12
For example, let's try this with number 12. 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 that 12 = 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 that 6 = 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 number 45, for example. We begin with the smallest prime number: 2. 45 divided by 2 does not give 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 that 45 = 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 that 15 = 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 * 5 You 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." You find factors of your number, and then factors of these factors, etc., until you arrive at prime numbers.
For example, if you want to factor 24, 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 a factor 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 factor 630. Because there is a zero on the end you know it has 10 as a factor. It can be written 63 * 10. Both of these factors can be factored further. Ten is 5*2 and that's all. 63 is 9*7, which gives the prime 7 and also 9 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 (the leaves on the tree) are prime 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 in increasing order like 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 to factor 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 to break 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: to break 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 number 245. There are two main ways to find the factors. One is to methodically go through all the possible prime factors and 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 a 2 in this number? Divide by 2, and you find that it doesn't divide evenly. How about 3? 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 we try 5:
___49_
5 ) 245
It goes evenly, so we know that
245 = 5 * 49
We'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 first check whether there is another 5 in 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
so
245 = 5 * 7 * 7
Since 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 often see 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 is divisible by 5, so we would divide by that first. Then when we see 49, we should recognize that as a square, 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