How to Prime Factor a Number

Factoring is sort of the opposite of multiplying, but more creative than division. To factor a number what we want to do is find numbers to multiply and get it, for example we can factor 15 as 3x5, and we can factor 12 as 2x6 or 3x4. Some numbers can be factored many different ways, but others can't be factored very many ways at all. All numbers can be factored as themselves times 1, but that's not very interesting.
 

Natural numbers bigger than 1 that can only be factored as themselves times 1 are called primes. The opposite of prime is composite. Numbers that can be factored in more interesting ways are called composites. 1 is neither prime nor composite, it isn't in the game, probably partly because in earlier times it wasn't regarded as a number.

How to Determine if a Number is Prime

A prime number is only divisible by 1 and itself, so to check whether a number is prime, you need to test each number between 2 and the number minus 1 to make sure none of them divide evenly into the number. That sounds like a lot of work, but actually it can be considerably shortened.

First, you really only need to test the primes, because if a composite number divided evenly into the number, then its factors would as well. For example, you can tell that 54 isn't prime, because it is divisible by 6, but you can also tell because it is divisible by 2 and 3. You can see that this sort of thing will always happen by factoring the factors and regrouping.

54=6x9=2x3x9=2x(3x9)=3x(2x9)

Second, you don't really have to go up anywhere near as high as the number minus 1 in your tests. Let's say, for example that you are trying to figure out whether 97 is prime. It isn't divisible by 2, 3, 5, or 7. I claim from that we know that it must be prime. Here's why.

The next prime after 7 is 11. Suppose it were divisible by 11. Then 11xN would be 97 for some number N. Now what about that number N? How big can it be? If it were bigger than 10 say, what would happen. 11xN would be bigger than 110, so certainly not 97. So N must be smaller than 10. But that would mean that 97 would have a factor that is less than 10, and therefore a prime factor that is less than 10, but we have already seen that it is not divisible by 2, 3, 5, or 7, the only prime numbers less that 10.

The trick here was that 10² is larger than 97. In general if you find a number whose square is larger than your number then if your number is divisible by anything larger than that number, then it has to also be divisible by something smaller than it, namely the other number in the factorization. So, for example, 88 is divisible by 11, because it is 11x8, but that means it is also divisible by 8. That means that when testing to see if a number is prime, once you find a number whose square is larger than  your number, you don't need to go beyond that number. A nice special case of this that comes up often is that for any number less than 100, you never need to go beyond 7, because 7 is the largest prime under 10, and 10²=100.

As for the task of testing for divisibility, one way to do this is simply divide it out, by there are a couple of tricks as well. For some numbers there are special shortcut tests that you can use. The most useful ones for prime factoring are the ones for 2, 3, and 5. You probably already know the ones for 2 and 5, but the one for 3 may not be familiar to you, and it is very useful.
 

2 A number is divisible by 2 if the last digit is divisible by 2, which means it must be 2, 4, 6, or 8. 3 A number is divisible by 3 if the sum of the digits is divisible by 3. 5 A number is divisible by 5 if the last digit is divisible by 5, which means it must be 0 or 5. 7 Unfortunately there isn't a very good trick for 7, so usually for 7, you just have to divide it out.

In practice most of the time when you are trying to find out whether a number is prime it will be less than 100, so what you do is apply the tricks for 2, 3, and 5, and if it isn't divisible by one of them, you divide by 7, and if that doesn't work, then you know it is prime.

Occasionally you might have to deal with a number larger than 100, and then you might have to test 11 or even 13, but do realize that in order to need to check 11, the number needs to be larger than 11²=121, and in order to need to check 13, it must be larger than 13²=169.

There is a trick you can use for 11 if you want. To see if a number is divisible by 11, add up ever other digit, and then add up the remaining digits. If you get the same thing, then the number is divisible by 11. So for example with 121, 1+1=2, and 2 is the remaining digit. 1243 would also be divisible by 11, since 1+4=2+3.

Short Division

Another helpful technique to know before we start prime factoring is a shortcut for long division for use with small divisors call short division. In short division you write the long division sign upside down and you do the multiplying and the subtraction in one step and express the remainder kind of like a carried number. Here's an example.

876543÷7

To do this by short division we make the long division symbol upside down and carry the remainders like this.

7 goes into 8 once, 1 times 7 is 7, 8-7=1, so that is 1 left over, so we carry that 1 to the next place, writing it little next to the 7. Then we continue saying 7 goes into 17 twice with 3 leftover, carry the 3, 7 goes into 36 five times with 1 leftover carry the 1 to the 5, 7 goes into 15 twice with 1 leftover carry the 1 to the 4, 7 goes into 14 twice with nothing leftover. Then in the final step 7 goes into 3 zero times with a remainder of 3.

Prime Factoring

Now I think we are ready for some prime factoring. The idea behind prime factoring, as apposed to just any old factoring, is to factor and then keep factoring the factors until you can no longer factor anything anymore, namely until you have it written as one big product of prime numbers, because the numbers that you can no longer factor will be by definition prime numbers. For a good example let's take a number that can be factored in many ways, 60. There are several different ways that you can factor 60.

60=1x60
60=2x30
60=3x20
60=4x15
60=5x12
60=6x10

The idea is to just start with one of these, it doesn't matter which one, except that 1x60 won't get you anywhere, and then factor each factor, and then the factors of the factors, and so on until you can do no more.

Let's try 6x10, since that would probably be the easiest one to see. We can factor 6 into 2x3, and 10 into 2x5. Replacing 6 with 2x3 and 10 with 2x5, this becomes

60=2x3x2x5.

2, 3, and 5 are all prime numbers, so we have prime factored 60. All we have to do now is neaten our answer up a bit. It is customary to write prime factorizations in increasing order, that is with the smallest numbers first, so by that custom it is better to write our answer like this.

2x2x3x5

It is also customary to use exponents as a shorthand when we have repeated multiplication. See the whole numbers part of my article Integer Exponents if you need some review with exponents.  By using exponents to write the repeat multiplication we would write the final answer for the prime factorization of 60 as

2²x3x5.

One interesting thing about prime factoring is that no matter how you start, you will in the end get the same factorization. If instead of starting with 6x10, we had started with 4x15, we would have factored 4 into 2x2, and 15 into 3x5, and gotten

2x2x3x5=2²x3x5.

If we had started with 5x12, we would have left 5 as is and factored 12 into 2x6 or 3x4. If we had factored it into 2x6, we would have factored 6 into 2x3 and gotten

5x2x2x3=2²x3x5,

and if we had factored it into 3x4, we would have factored 4 into 2x2 and gotten

5x3x2x2=2²x3x5.

And I'll leave the checking of the rest of the possibilities as exercises for the students.

There are a couple of good ways to keep track of things when you are prime factoring. One of them involves making trees and the other involves short divisions one on top of the other.

The Tree Method

The method involves drawing branches for a tree every time you factor, and then at the end you put together the ends of the branches for you prime factorization. So here is how the prime factorization of 60 would go using this method. For variety I am starting with a different factorization this time and first factoring 60 into 3x20, drawing branches for the 3 and the 20. Then I factor the 20 into 10 times 2, drawing 10 and 2 branches. Since 3 is prime it doesn't branch. The 2 is also prime, so it doesn't branch either, but I factor the 10 into 2 and 5, making branches for them, and now I am down to only primes. Then for the factorization all I have to do is put together all of the ends of the branches in numerical order and use exponents to indicate repeated multiplication, so I again get an answer of

2²x3x5.

The Short Division Method

This method isn't really as good in that for most problems it really takes longer than the tree method, but it has an advantage that a lot of people like, which is that it at least seems more systematic in that you always do it the same way, and also you will always get the factors in the correct order by using this method. What you do in this method is you start with the first prime, which is 2 and ask yourself whether the number is divisible by it. If it is, use short division to divide it by 2, and then continue with the answer you get from the division and ask yourself if that is still divisible by 2. If it is, divide that by 2. Eventually you will get an answer that is not divisible by 2, so then you ask yourself whether it is divisible by 3, and then continue on in this way with 5, 7, and the rest of the primes until you get an answer that is prime. Then the numbers along the side and the final answer will be the prime factorization written in the proper order. Here is how we would factor 60 using this method. Is 60 divisible by 2? Yes. So we divide it out and get 30. Is 30 divisible by 2? Yes, so we do it again. Is 15 divisible by 2? No, so we try 3. 15 is divisible by 3, so we divide it out and get 5, which is prime, so we are done. The we read the numbers from top to bottom and around in order to write down our answer.

2²x3x5

More Examples

Example 1:

100

Short Division:

Is 100 divisible by 2. Yes, so we divide it by 2 and get 50. Is 50 divisible by 2. Yes, so we divide it by 2 and get 25. Is 25 divisible by 2. No. How about 3. The sum of the digits is 2+5=7, which is not divisible by 3, so it is not divisible by 3. Is it divisible by 5. Yes, so we divide it by 5 and get 5.

Tree:

When we use this method we can factor it any way we want at the beginning. You can just factor it the first way you see, but it usually goes quickest if you factor it as evenly as possible so that you will get down to smaller numbers that you can more easily see how to factor quicker.

Either way we do it in the end we have two 2's and two 5's, so that's

2²x5².

Example 2

81

Tree:

Short Division:

81 is not divisible by 2, so we ask ourselves if it is divisible by 3, and since the sum of the digits is 9, we know it is, so we divide it by 3. 27 is again divisible by 3, so we divide by 3 again, and then we get 9, which is again divisible by 3, and the answer is 3, which is prime, so we are done.

So now whichever way we do it, we have four 3's, so the answer is

3⁴.

Example 3

9900

Short Division:

Okay, here's a long one to really show how this method works. 9900 is divisible by 2, so we divide it by 2 and get 4950. 4950 is still divisible by 2, so we divide it by 2 again and get 2475. 2475 is not divisible by 2, so we got to the next prime, which is 3, and ask if it is divisible by 3. The sum of the digits is divisible by 3. I can tell this because the sum of the first two is 6 and the sum of the second two is 12, which are both divisible by 3. So from that we know that it is divisible by 3, so we divide it by 3 and get 825. The sum of the digits of 825 is 15, which is divisible by 3, so 825 must by divisible by 3, so we divide it by 3. By the way, even if it wasn't clear that 825 was not divisible by 2, we wouldn't have to check for that, because 2475 wasn't divisible by 2, and once you have taken out a factor it is gone. So anyway, after we divide 825 by 3, we get 275, and for 275 we don't have to ask whether it is divisible by 2, but we do still have to ask whether it is divisible by 3, but it isn't, because the sum of the digits is 17, which is not divisible by 3. So know we go to the next prime, which is 5. 275 is clearly divisible by 5, so we divide it by 5 and get 55, which is also divisible by 5. We divide it by 5 and we get 11. 11 is prime, so we are done.

Tree:

This is also a very good problem to show that the tree method can be a lot quicker and easier that the short division method, because here it is very easy to factor out a factor of 100 and get it down to much smaller numbers right from the beginning. Then both 99 and 100 are easy to factor. The only disadvantage is that we have to do some sorting in the end and make sure to to include all of the ends of the branches, including the 11.

However we do it, we have two 2's, two 5's, two 3's, and one 11, so that's

2²x3²x5²x11.

Example 4

910

Tree:

It's easy to factor 910 into 91 times 10, and then it is easy to factor the 10, but what about the 91? 91 is one of those annoying numbers that looks like it is prime, but it isn't. There is only one prime in the 90's, and it is easy to forget which one it is. 93, 95, and 99 clearly aren't prime, because 93 and 99 are divisible by 3, and 95 is divisible by 5, so it is either 91 or 97. It turns out that it is 97, because 91 is divisible by 7. It is clearly not divisible by 2 or 5, and since the sum of the digits is 10, it is not divisible by 3, so 7 is the only possibility, and the only way to find this out is to try it, either by short division or by the calculator. However you do it, if you don't make a careless error along the way, you should be able to find that 91 is indeed divisible by 7, and it is 7 times 13, and 13 is another prime numbers, so this factorization brings us to the end of the limbs.

Short Division:

910 is divisible by 2, so we can divide it by it and get 455. 455 is no longer divisible by 2, so we need to try 3, and it is not divisible by 3, because the sum of the digits is 4+5+5=14, so we try 5, and it is divisible by 5. So we divide it by 5 and get 91. 91 is not divisible by 5, so the next number to try is 7. There's no easy way for 7, so we just have to try it, and this time it worked and we got 13.

So the prime factorization is

2x5x7x13.

Example 5

370

Short Division:

370 is divisible by 2, so we divide by 2 and get 185. 185 is not divisible by 2. Is it divisible by 3? The sum of the digits is 1+8+5=14, which is not divisible by 3, so 185 is not either, so try 5. It is divisible by 5, so we divide by 5 and get 37. Is 37 divisible by 5? No. Now for 37 that is as we need to go to tell that it is prime, because 7x7=49, which is bigger than 37, so we are done.

Tree:

Notice how much easier the tree method is for this one, because of being able to factor out the 10 right away instead of first dividing by 2 and then by 5. Then breaking down the 10 is no problem, because we all know that 10 is 2 times 5. The 37 is a bit more problematic, because at this point we haven't yet tested it for divisibility by 2, 3, and 5, but it is easy to see that it is not divisible by any of these, so since it is smaller than 7x7, it can't be divisible by anything larger, so it must be prime.

So we have three factors that each occur once, 2, 5, and 37, so the factorization is

2x5x37.

Example 6

143

This one is a bit tricky no matter how you do it. Maybe it's prime. It's not divisible by 2,3, or 5. How about 7? No, if we divide it by 7, we get 20 R 3. But since it is bigger than 100, we might have to try 11. 11x11=121, which is less than 143, so it could be divisible by 11. In fact if we use the test I mentioned for 11's, adding up the alternate digits, we get 1+3=4, which is indeed also the sum of the remaining digit 4, so it is divisible by 11, and if we divide it by 11 we get 13, which is also prime, so the factorization is

11x13.

For such a small factorization, we don't really need any method of keeping track of things, but if we did want to show what each of the two methods would look like for it, here is how that would go.

Tree:

Short Division: