## What is Prime Factorization?

*Factorization* means that you break a number into its factors. To do *Prime* Factorization, after you break your number into factors, you break the factors into factors, then you break the factors of the factors into factors, and so forth and so on, until you’ve only got prime numbers left. The point of prime numbers is that they can’t be broken into smaller factors. So prime factorization means you’ve broken down a number as far as it is possible to do so.

## A Gross Prime Factorization Example:

Sometimes the easiest way to explain something starts with an example. Let’s take a number and break it into components. How about a number with a special name? Let’s factor a gross. How do you factor 144?

Well, a gross is special because it’s a dozen times a dozen. (“A dozen” is another number with a special name – a dozen means 12.) So 144 can be factored into 12 times 12. But 12 is a composite number. Calling a number “composite” simply means we can factor it. Anyways, 12 is 6 times 2. So we can replace one of our dozens with 6 times 2, because they are exactly the same thing. Now we’ve got 12 x (6 x 2).

But wait! Since, 3 times 2 makes 6, we can replace our 6 with 3 times 2. Now we’ve factored our gross into 12 x ((3 x 2) x 2).

### Why? Because We Feel Like It.

But we’re not done — that first 12 can still be factored. Not only is twelve 6 x 2, it’s also 4 x 3. so we can replace that first 12 with 4 x 3. Why use 4 x 3 instead of 6 x 2? Because we feel like it. Wait! Can you do that in math? Yes we can, and we’ll talk about it more soon. By the way, mathematicians have a special word for when it’s OK to do something just because you feel like it: they say it’s “*Arbitrary*.”

Now we say that 144 is (4 x 3) x (3 x 2) x 2. There’s one composite number left: 4 is 2 times 2. Factoring it gives us ((2 x 2) x 3) x ((3 x 2) x 2). Those are all prime numbers, so we have found the prime factorization. However, since it doesn’t matter what order you multiply numbers in, we can get rid of the parenthesis, and change the order. Let’s move all the twos so they’re together and all the threes are together. The prime factorization of 144 is 2 x 2 x 2 x 2 x 3 x 3.

## What does the Unique Factorization Theorem have to do with it?

Some questions only have one answer. Some questions have more than one correct answer. Did you notice that in the example above, there were a lot of choices along the way about different ways to do things? (We just drew attention to one of those arbitrary choices.) When you’re factoring a number with lots of factors it feels that this is the kind of question with lots of answers, but the Unique Factorization Theorem says that it’s not. Even though there’s lots of ways to do the prime factorization, the theorem says that no matter what arbitrary choices you make, you’ll get the same answer in the end.

## What is the Unique Factorization Theorem?

- Every whole number greater than one is the product of a unique list of prime numbers (or just itself if it
*is*a prime number). - The list of factors can have the same prime number in it more than once.
- If you change the order of numbers in the list, it’s still considered to be the same list.
- Unique means that there is only one possible list of prime number factors for any original number.

## What does the Unique Factorization Theorem mean for Prime Factorization?

At it’s essence, Prime Factorization means breaking a number into a list of all of its prime factors. The Unique Factorization Theorem says that no matter how you go about doing Prime Factorization (and some numbers have *lots* of correct ways to do it) you will end up with the same single correct answer.

## How To Remember The Unique Factorization Theorem

This may all make sense but seem a bit hard to remember. What we need now is a way to make it easy to remember. A simple way of visualizing and remembering the Theorem is to think of the list of prime factors as being **a recipe for a number**. There’s only one recipe for any given number.

## Multiplication & Addition

Sometimes, students can get a little confused at this point between multiplication and addition. Out of context, that seems silly, but there is a good reason. What happens is we successfully adopt the correct image in our mind of breaking down a number into parts, but breaking down can be done either in the sense of addition or multiplication. Avoid this trap by focusing on the word *factorization* in both Prime *Factorization* and The Unique *Factorization* Theorem. Factorization means multiplication. The reason behind it has to do with the fact that if you are breaking apart a number by addition, you can always break it into smaller parts until you’re left with a boring bunch of 1s. In the case of multiplication, the fact that some numbers are prime and others are composite makes things interesting.

## The Unique Factorization Theorem and The Fundamental Theorem of Arithmetic

The Unique Factorization Theorem is just another name for The Fundamental Theorem of Arithmetic. In fact, The Unique Factorization Theorem is probably a better name, because it reminds everyone of what it says. After all, “arithmetic” could possibly refer to addition, whereas the word “factorization” helps keep people from forgetting that the theorem only refers to multiplication of prime factors.

## Why is the Prime Factorization of a number sometimes written with exponents?

It just makes it easier to read. For example, the factorization “recipe” for a *gross* (144) is four 2s and two 3s. Since all those factors are multiplied, we can write it as 2 x 2 x 2 x 2 x 3 x 3. Your eyes might get lost seeing how many 2s there are. Since exponents show that a number is multiplied by itself a certain number of times, it can be written as 2^{4} x 3^{2}, which makes it really clear how many 2s there are, and how many 3s.

# How do you find the Prime Factorization of a number?

- Find any number that is a factor. If the number is small enough to be on a 10 x 10 times table, your mind will probably just see the factor. Otherwise, you can systematically try numbers, or even just hope for a lucky guess.
- Divide the number by the factor you found to give another factor. Make a list of all the factors found so far.
- If any of the factors is composite, it will have to be broken into prime factors as well (see step 1).
- Once every factor, and factor of a factor, and factor of a factor of a factor, and so forth, is a prime number, the prime factorization is complete.
- It can be a good idea to multiply all the factors together to make sure that no mistakes were made. If everything is correct, the product of all the prime numbers should give the original number.

### The Difficult Part – Getting Started

*Step 1 can be hard.* There are a few little tricks, such as: if the number is even, then 2 is a factor; if the last digit is 5, then 5 is a factor; and if the last digit is ‘0’ then 10 is a factor. If the number is really big, and there are no obvious tricks, it can take a lot of trial and error to find a factor. Having a list of prime numbers, and just trying to divide by prime numbers can save time in such a case. Because seeing the factors of numbers can be difficult, and is so important for many math problems, we created a game that helps you get good at factoring and recognizing prime numbers.

### The Interesting Part – Recursion

*Step 3 is interesting.* The main problem is broken into subproblems that are solved in the same way as the main problem. This problem solving technique is common in computer science, where it is known as a *recursive algorithm*.

## Using Factor Trees

If keeping track of all the factors gets complicated, we sometimes make a kind of picture called a Factor Tree. In addition to keeping the factors organized, it allows us to avoid having to recopy all the known factors each time we need to break down a composite factor.

Another great thing about factor trees is that they can give a really clear picture of the Fundamental Theorem of Arithmetic. In the next example, two different factor trees of 144 are shown. Although it is broken into factors differently, once it is reduced all the way to prime factors, the same primes are revealed – four 2s and two 3s.

## Computers Can Help Solve Really Difficult Cases

In difficult cases, computer programs can find the prime factorization of a number using basically the same method a person would use, although sometimes, slightly different tricks make it go faster. For really big numbers, even the fastest, most powerful computers have trouble finding prime factorizations!

Here’s an example of a C program that can solve unique factorization problems.

Next Topic: Least Common Denominators (LCDs):