THE PRIME FACTORIZATION THEOREM

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:

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 $\,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.

First helpful observation:
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!

Second helpful observation:
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.)