﻿ The Prime Factorization Theorem
THE PRIME FACTORIZATION THEOREM
• PRACTICE (online exercises and printable worksheets)
• Before reading this section, you may want to review: Prime Numbers

As shown in the prior section, the numbers $\,2, 3, 4,\, \ldots\,$ can be uniquely expressed as a product of primes.
Just keep ‘breaking them down’ into smaller and smaller factors until only prime numbers remain.

For example:

 $360$ $=$ $36$ $\cdot$ $10$ $=$ $6$ $\cdot$ $6$ $\cdot$ $2$ $\cdot$ $5$ $=$ $2$ $\cdot$ $3$ $\cdot$ $2$ $\cdot$ $3$ $\cdot$ $2$ $\cdot$ $5$
OR
 $360$ $=$ $4$ $\cdot$ $90$ $=$ $2$ $\cdot$ $2$ $\cdot$ $9$ $\cdot$ $10$ $=$ $2$ $\cdot$ $2$ $\cdot$ $3$ $\cdot$ $3$ $\cdot$ $2$ $\cdot$ $5$
OR
 $360$ $=$ $6$ $\cdot$ $60$ $=$ $2$ $\cdot$ $3$ $\cdot$ $6$ $\cdot$ $10$ $=$ $2$ $\cdot$ $3$ $\cdot$ $2$ $\cdot$ $3$ $\cdot$ $2$ $\cdot$ $5$

No matter how the number is ‘broken down’, you'll always get to the same place,
except for possibly different orderings of the factors.

In the example above, you always get $\,360 = 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5\,$.
Three factors of $\,2\,$, two factors of $\,3\,$, and one factor of $\,5\,$.

This idea is formalized as:

## The Prime Factorization Theorem

 THEOREM the Prime Factorization Theorem Every counting number greater than $\,1\,$ has a unique expression as a product of primes.

## Notes on the Theorem:

• Alternate name:
The Prime Factorization Theorem also goes by the name ‘the Fundamental Theorem of Arithmetic’.
• Uniqueness:
In a multiplication problem (a product), the order and grouping of factors doesn't matter
(as per the commutative and associative properties of multiplication ).
Uniqueness refers to which prime(s) appear, and how many of each factor you have.
For example, all the following are the same (unique) expression:

$2\cdot 3\cdot 3\cdot 5\cdot 5\cdot 5$                 $2\cdot 3^2\cdot 5^3$                 $(2\cdot 3\cdot 5)(3\cdot 5)(5)$                 $2(3\cdot 5)^2\cdot 5$

Why? Because each has one factor of $\,2\,$, two factors of $\,3\,$, and three factors of $\,5\,$.
• Prime factors are needed for uniqueness:
The phrase ‘as a product of primes’ is essential in the theorem.
Numbers do not necessarily have a unique expression as a product of any 'ole factors.
For example,   $\,20 = 2\cdot 10\,$   or   $\,20 = 4\cdot 5\,$.
The factorizations $\,2\cdot 10\,$ and $\,4\cdot 5\,$ are different!
• Prime factorization of primes:
If a number is itself prime, then its expression as a product of primes is particularly simple—it's just itself!
For example, here's the prime factorization for the number five: $\,5\,$
The prime factorization for the number five is one factor of $\,5\,$.
• Conventional and convenient way to state the prime factorization:
It is conventional and convenient to list the prime factors in increasing order, and to use exponent notation.
For example: $\,2250 = 2\cdot 3^2\cdot 5^3\,$
You'll be asked to use this representation in the exercises below.

## Why isn't the Number $\,1\,$ Considered to be Prime?

If we decided to call the number $\,1\,$ prime,
then we lose the uniqueness of representation guaranteed in the Prime Factorization Theorem.
For example, here's what we'd have to contend with:
 representation of numberas a product of ‘primes’ factors of $\,2\,$ factors of $\,3\,$ factors of $\,1\,$ $6 = 2\cdot 3$ one factor of $\,2\,$ one factor of $\,3\,$ no factors of $\,1\,$ $6 = 2\cdot 3\cdot 1$ one factor of $\,2\,$ one factor of $\,3\,$ one factor of $\,1\,$ $6 = 2\cdot 3\cdot 1\cdot 1$ one factor of $\,2\,$ one factor of $\,3\,$ two factors of $\,1\,$ ... and so on ...

To avoid this annoying situation, we don't call the number $\,1\,$ prime. Problem solved!

## An Efficient Method for Determining if a Number is Prime

Given a counting number greater than $\,1\,$, if you can find any factor other than itself or $\,1\,$, then it's not prime.

For example, the number $\,217,695\,$ is definitely not prime. Since the last digit is $\,5\,$, it's divisible by $\,5\,$.
Or, the number $\,927,856\,$ is definitely not prime. It's even, so it's divisible by $\,2\,$.

However, factors aren't always so obvious.
For example, is the number $\,1{,}327\,$ prime?
If you take the following (thorough, but inefficient) approach, it will take you a LONG time to get the answer:

Does $\,2\,$ go in evenly? No.
Does $\,3\,$ go in evenly? No.
Does $\,4\,$ go in evenly? No.
Does $\,5\,$ go in evenly? No.
Does $\,6\,$ go in evenly? No.
... and so on ...

Let's start improving on this inefficiency.

If a number has any factor (not necessarily prime), then it must have a prime factor.

For example, if a number is divisible by $\,10\,$ (which isn't prime), then it is also divisible by $\,2\,$ and $\,5\,$ (the prime factors of $\,10\,$).
Therefore:

To determine if a number is prime, you only need to check if primes go into it evenly.

Now we have far fewer questions:

Does $\,2\,$ go in evenly? No.
Does $\,3\,$ go in evenly? No.
Does $\,5\,$ go in evenly? No.
... and so on ...

It ends up that there are $\,217\,$ primes less than $\,1{,}327\,$, so this would still be a lot of checking.
We can do much better still!

The factors of a number $\,N\,$ always occur in pairs:
one factor in the pair is less than or equal to $\,\sqrt{N}\,$,
and the other factor is greater than or equal to $\,\sqrt{N}\,$.

For example, $\,4\cdot 11 = 44\,$, and $\,\sqrt{44}\approx 6.6\,$.
The first factor, $\,4\,$, is less than $\,\sqrt{44}\,$.
The second factor, $\,11\,$, is greater than $\,\sqrt{44}\,$.

A moment's reflection should convince you that this is true.
If two numbers are both less than $\,\sqrt{N}\,$, then their product is less than $\,N\,$.
If two numbers are both more than $\,\sqrt{N}\,$, then their product is more than $\,N\,$.
Therefore:

To determine if a number is prime,
it is only necessary to check the prime factors
that are less than or equal to its square root.

If none go in evenly, then the number is prime!

Now, back to our original question: is $\,1{,}327\,$ prime?
Note that $\,\sqrt{1327} \approx 36.4\,$.
There are only eleven primes less than $\,36.4\,$:   $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, and $31$.
It's pretty quick to check that none of these primes go into $\,1{,}327\,$ evenly.
Therefore, $\,1{,}327\,$ is prime!

There's a more convenient way to answer the question (but your teacher might not let you use it on a quiz or test)!
Zip up to WolframAlpha and type in:   Is 1327 prime?
Voila!

Master the ideas from this section
by practicing the exercise at the bottom of this page.

When you're done practicing, move on to:
Relatively Prime Numbers and Related Concepts

CONCEPT QUESTIONS EXERCISE:
On this exercise, you will not key in your answer.
However, you can check to see if your answer is correct.
PROBLEM TYPES:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
AVAILABLE MASTERED IN PROGRESS
 (MAX is 17; there are 17 different problem types.)