Prime Numbers and Prime Factorizations

Quick Navigation Video Lectures Examples

In Math . . .

A number is a prime number if it has no factors except one and itself.

In English . . .

A prime number is one that no other number goes into evenly. For example, 12 isn't a prime number because 12 / 3 = 4. On the other hand, 7 is a prime number because the only numbers that divide seven evenly are 7 and 1.

Quick Tip - Which One Did You Find?

Prime numbers are exceptionally usefull - most of modern cryptography is based on them. Unfortunately, they're also very mysterious. For example, no one has every been able to figure out a pattern to how they occur. This makes finding prime numbers exceptionally difficult. The easiest way to do it is just to divide a number by every number smaller than it and see if anything goes into it evenly. Unfortunately, for exceptionally large numbers, i.e. ones with hundreds of digits which are the kind needed to do cryptography, even the most powerful computer would take decades to work through all the required numbers.

So how can you tell if a number is prime or not? For our purposes, the easiest way is just to the number you're given by every number smaller than it. If anything goes into it evenly then the answer is no. If nothing goes into it evenly then the answer is yes.

To make things easier as we go along, here's a list of the prime numbers less than 100.

3	5	7	11	13	17	19	23	29	31
37	41	43	47	53	59	61	67	71	73
79	83	89	97

Don't take my word for that list. Try to divide those numbers by any other number (except one and the number itself) and you'll see that the result has a decimal part.

One of the most important tasks, you'll need to do with prime numbers is writing out the "prime factorization" of a number.

In Math . . .

The prime factorization of a number is the number written as a product of prime numbers.

In English . . .

What we want to do here is rewrite the original number as a bunch of prime numbers mutiplied together. For example, 3 · 3 · 5 is the prime factorization of 45 because 3 · 3 · 5 = 45 and 3 and 5 are both prime numbers. On the other hand, 9 · 5 would not be the prime factorization of 45. It's true that 9 · 5 = 45 but this can't be the prime factorization because 9 isn't a prime number.

The procedure for finding the prime factorization of a number goes like this:

Is the number divisible by 2? If it is then rewrite the number as 2 times a smaller number.
Is the smaller number divisible by 2? If it is then rewrite the smaller number as 2 times an even smaller number. Repeat this step until you can't divide 2 into the smaller number any more.
Try to divide the smaller number from step 2 by the next prime number on the list. Repeat steps 1 and 2 with every prime number that's smaller than the original number.

Videos

Lectures

Prime Numbers

Prime numbers are numbers with only two distinct factors - 1 and the number itself. In this lecture, we'll look at what prime numbers are and some helpful rules for determining if a number qualifies. (lecture slides)

Prime Factorizations

In this lecture, we're going to look at how you can use what's called a factor tree to find the prime factorization of a number. (lecture slides)

The Fundamental Theorem of Arithmetic

An important question about prime factorizations is, "Are they unique?" In this lecture, we'll look at an example that points us toward the answer that's described in the Fundamental Theorem of Algebra. (lecture slides)

Example 1

Find the prime factorization of 45.

This is the number that I used in the "In English ..." discussion above. Here's how I went about finding the prime factorization.

Two doesn't go into 45 so we go to the next prime number on the list.
Three goes into 45.	45 = 3 · 15
Three goes into 15.	45 = 3 · 3 · 5
5 is prime so the prime factorization of 45 must be 3 · 5 · 5. Using exponents, we can simplify that to 3 · 5²

Example 3

Find the prime factorization of 550.

Two goes into 550.	550 = 2 · 275
Two doesn't go into 275 so we go to the next prime number on the list.
Three doesn't go into 275 so we go to the next prime number on the list.
Five goes into 275.	550 = 2 · 5 · 55
Five goes into 55.	550 = 2 · 5 · 5 · 11
11 is prime so the prime factorization of 550 must be 2 · 5 · 5 · 11.

Example 2

Find the prime factorization of 180.

Two goes into 180.	180 = 2 · 90
Two goes into 90.	180 = 2 · 2 · 45
Two doesn't bo into 45 so we move on to the next prime number on the list.
Three goes into 45.	180 = 2 · 2 · 3 · 15
Three goes into 15.	180 = 2 · 2 · 3 · 3 · 5
5 is prime so the prime factorization of 180 must be 2 · 2 · 3 · 3 · 5. Using exponents, we can simplify that to 2² · 3² · 5.

Example 4

Write the prime factorization of 14365.

Big numbers may look intimidating but all you have to do is work through the prime numbers just like in the previous examples. (Having a calculator helps with the division.)

Two doesn't go into 14365 so we move on to the next prime number on the list.
Three doesn't go into 14365 so we move on to the next prime number on the list.
Five goes into 14365.	14365 = 5 · 2873
Five doesn't go into 2873 so we move on to the next prime number on the list.
Seven doesn't go into 2873 so we move on to the next prime number on the list.
Eleven doesn't go into 2873 so we move on to the next prime number on the list.
Thirteen goes into 2873.	14365 = 5 · 13 · 221
Thirteen goes into 221.	14365 = 5 · 13 · 13 · 17
Seventeen is prime so the prime factorization of 14365 must be 5 · 13 · 13 · 17. Using exponents, we can simplify that to 5 · 13² · 17.