Prime Factorization

What is the Unique Factorization Theorem?

The Unique Factorization Theorem says:

  • Every whole number greater than one is the 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 is Prime Factorization?

Prime Factorization means breaking a number into that list of all of its prime factors. The Unique Factorization Theorem says that no matter how you go about doing Prime Factorization, you’ll get the same answer in the end.

How To Remember The Unique Factorization Theorem

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.

The one and only recipe for the number 28. Ingredients: two numbers 2s, one number 7. Directions: Combine all ingredients by multiplying. Use immediately or save for later.

Every Number has a Unique Recipe.

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 (that is 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 24 x 32, which makes it really clear how many 2s there are, and how many 3s.

How do you find the Prime Factorization of a number?

  1. 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 try for a lucky guess.
  2. Divide the number by the factor you found to give the other factor. Make a list of all the factors found so far.
  3. If any of the factors is composite, it will have to be broken into prime factors as well (see step 1).
  4. 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.
  5. 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.

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.

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.Use the Factor Tree of 144 to find its prime factorization.

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.

Two different factor trees of 144; the unique factorization theorem guarantees all factor trees of 144 have the same leaf nodes.

Computers Can Help Solve Really Difficult Cases

In difficult cases, computer programs can be used to try to find the prime factorization of a number using basically the same method a person would use, although sometimes, slightly different tricks are used to 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.

The complete C language code of a program for breaking numbers into their prime factors.

A program written in the C language for finding the prime factorization of numbers

Next Topic: Least Common Denominators (LCDs):

About this Bubbly Primes Math Help Page