BMCC: Math Tutorials: Numbers:
Prime Numbers
Quick links to topics on this page:
Prime and Composite Numbers
Prime Factorization
In the previous section we saw how to determine the factors for any given product. For fairly small numbers, say with two digits, the process is fairly quick and simple because the factors are mainly numbers for which we have memorized multiplication tables, and the "work" can almost be done in your head, simply writing down which numbers you've tested and which ones proved to be factors so you don't lose your place. For larger products, the process is just as simple, but the factors being tested are large enough that most people don't have the multiplication factors memorized, so a calculator is necessary. Extremely large numbers require enormous amounts of time on computers to determine all of their factors, or whether they have any factors at all besides themselves and the number 1. However, in spite of the vast computational power needed for these large numbers, the process of determining their factors is basically the same method you learned in the previous section. If you had enough time and patience, you could factor a very large number with just a pencil and paper.
Note that in the previous paragraph I mentioned that some products might not have any factors besides themselves and 1. We've already seen some examples like this, such as the number 3. There are no whole numbers that can be multiplied together to produce the product 3, except for 3 itself and 1. Other small numbers that have the same quirk include 5, 7, and 11-- in each case, the product n can only be produced by multiplying n times 1, and there are no other factors.
Numbers that have no factors except themselves and 1 are called prime numbers. Most of the examples in the previous section dealt with products that did have factors in addition to themselves and 1-- such numbers with additional factors are called composite numbers. Most numbers are composite numbers, and as numbers get bigger, prime numbers become less abundant on average. However, there is not any upper limit on how large a number can be and still be prime, and there is much research being done on discovering large prime numbers. Because no formula has ever been found that accounts for all of the known prime numbers, prime numbers cannot be calculated. Instead, each number must be tested individually to see if it has any factors. Only when it is demonstrated that a number has no factors besides itself and 1 has the number been "proved" to be prime.
Note that all prime numbers will be "odd," because all "even" numbers can be evenly divided by 2, and so even numbers will always be composite. Not all odd numbers are prime, though. For instance, 9 is a composite number (3 times 3), as is 15 (3 times 5).
Below is a list of all of the prime numbers less than 50. Note that the number 1 is not defined as a prime number.
As an aside, on June 1st, 1999, the largest prime number discovered to date was announced. Expressed in exponential notation, the number is
This number has 2,098,960 digits. It took a 350 megahertz Pentium II computer more than 3 weeks of continuous running (spread out over 111 days) to prove that this number had no factors. See what I mean about needing time and patience if you tried to factor a very large number with pencil and paper?
We showed in the previous section on factoring how a list of factors could be determined for any product. If the product is composite, the factor list will include additional factors besides the number and 1. As an example, if you use the progressive method, you can determine that the factors for 24 are 1, 2, 3, 4, 6, 8, 12, and 24. Note that most of these factors are not prime: 4, 6, 8, 12, and 24 are all composite.
If a number is expressed as a product of its prime factors, that is prime factorization. What that means is that a factor pair that produces the product needs to be broken down until only prime numbers remain-- in other words, you want to factor the factors until all that remains is prime numbers. To do this you can select any of the factor pairs that produce the product. In this case the product was 24, so the factor pairs are 1 times 24, 2 times 12, 3 times 8, and 4 times 6. Start by selecting any pair except the one with 1 and the product-- let's choose 2 and 12.
What we want to do is break these factors down until only prime numbers remain. The first factor is 2. Since 2 is a prime number, it cannot be broken down into more factors. However, the second factor, 12, is not prime, and can be broken down further, such as into 2 times 6. Now, instead of expressing the product as 2 x 12, we have broken down the second factor so the product is expressed as 2 x 2 x 6. But 6 itself is still composite, and can be broken down into 2 times 3, so our expression for the product 24 is now 2 x 2 x 2 x 3. Now, finally, we have a list of numbers that are all prime, and cannot be broken down into smaller factors. We say that the prime factorization of 24 is 2 x 2 x 2 x 3.
What happens if we choose a different factor pair instead of 2 and 12? As it turns out, no matter which factor pair you start out with, you'll end up with the same prime factors. Let's go through the same process again for the product 24, but this time we'll start with the factor pair 4 and 6. In this case, neither factor is prime-- they can both be broken down into additional factors. We start out with 4 x 6 = 24 . 4 can be broken down as 2 x 2, which gives us 2 x 2 x 6 = 24 . 6 can be broken down as 2 x 3, so now we have 2 x 2 x 2 x 3 = 24 . This is exactly what we got the first time, with 24 expressed as the product of only prime factors. This is prime factorization.
For practice, determine the prime factorization for 24 by starting with the factor pair 3 and 8. You'll see that you end up with the same result obtained above for the other factor pairs for the product 24.
Next: Least Common Multiple
[Previous Page] -- [Next Page]
[Top of Page] -- [Tutorials Home Page]
[BMCC Home Page] -- [E-mail the Tutorial Coordinator]
