The Prime Factorization Theorem
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
Notes on the Theorem
-
Alternative 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:
$$ \begin{gather} \cssId{s26}{2\cdot 3\cdot 3\cdot 5\cdot 5\cdot 5}\cr \cssId{s27}{2\cdot 3^2\cdot 5^3}\cr \cssId{s28}{(2\cdot 3\cdot 5)(3\cdot 5)(5)}\cr \cssId{s29}{2(3\cdot 5)^2\cdot 5} \end{gather} $$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 number as 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 $\,1327\,$ 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:
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 $\,1327\,,$ 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 (nonnegative) 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:
If none go in evenly, then the number is prime!
Now, back to our original question: is $\,1327\,$ 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 $\,1327\,$ evenly. Therefore, $\,1327\,$ 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!