Activities for this section:

Prime Time

Prime numbers

Sometimes, when children start making lists of factors, they can start to notice things. Let’s make a couple of lists of factors and see that there are different types of things that can happen.

How do we know that we wrote down all of the factors of $24$? We did this in a systematic way by checking whether $1$, $2$, $3$, and so on were factors of $24$, and we continued until we had checked every number. We can see that $5$ is not a factor of $24$, and then when we check $6$ we find that it’s already on our list of factors. We could check that $7$ is not a factor of $24$, but we actually don’t need to do that if we notice that the numbers in the left column in our example are all smaller than the numbers in the right column. When we multiply $A \times B$ and get $24$, one of the numbers is smaller and the other is larger. Since $7$ is larger than the smallest number in the right hand column, if it was a factor of $24$ it would already have appeared paired with a smaller number from the left hand column. Another way to see this is to see that \[ 24 \div 7 \approx 3.43 \] which means that we have to multiply $7$ by a number that’s approximately $3.43$ in order to get $24$. This number would be between $3$ and $4$, and thus can’t show up in our list of whole numbers on the left. If we divided $24$ by $9$, we could get an even smaller quotient, which again does not already appear on our list. So, we are confident that this is the entire list of factors, even though we only needed to divide by $1$, $2$, $3$, $4$, and $5$.

Let’s do another example.

Notice that in this example, we wrote the factor $5$ but we didn’t write anything across from it. The reason for this is that $5 \times 5 = 25$ and we only want to write the factor $5$ once in our list. While $24$ had an even number of factors (every factor had a pair), $25$ has an odd number of factors. The difference is that with $24$, we don’t have any whole number $A$ so that $A$ multiplied by itself gives $24$. But we do have such a number for $25$. A number $N$ where we can find some whole number $A$ so that $A$ multiplied by itself is equal to $N$ is called a square number. So, we have said that $25$ is a square number and $24$ is not. We’ve also noticed, as some children do if they are playing with factors, that square numbers have an odd number of factors while non-square numbers (like $24$) do not.

We could still find a number $A$ so that $A$ multiplied by itself is equal to $24$, but this number would not be a whole number. In fact, we use special notation for this $A$ called the square root of $N$, written $A = \sqrt {N}$. As an example, we have \[ \sqrt{25} = 5 \] because \[ 5 \times 5 = 25. \] We could also write \[ \sqrt{24} = 4.89897\dots \] because if we took the infinitely long decimal above and multiplied it by itself, we would get exactly $24$. \[ 4.89897\dots \times 4.89897\dots = 24 \] There is one more thing to notice, here: the square root gives us the “turning point” in the table where we switch from the left-hand side of the table to the right-hand side. Notice that in our table for $24$, the last row was $4$ and $6$ since $4 \times 6 = 24$. When we divide $24 \div 4$ we get $6$, and $6 > 4$ so the quotient is larger than the divisor. But if we divide $24 \div 5$ we get 4.8, and $4.8 < 5$ where the quotient is smaller than the divisor. If we are dividing by numbers starting with $1$ and getting larger each time, the square root is the place where the quotient switches to be smaller than the divisor and we know that we are done making our chart.

Let’s look at one more example that will bring us to the main idea of this section.

In this case, we found exactly two factors: $1$ and $31$. Numbers that have exactly two factors are special enough that we will talk about them for the rest of this section.

Children begin learning about prime numbers in fourth grade alongside their work on factors and multiples. Let’s check out an application of our definition.

The number $1$ is a strange case, but our definition makes things clear. You might have seen the definition of prime numbers before written as numbers which have only $1$ and themselves as factors (not mentioning exactly two factors). Notice how this makes the case of $1$ more confusing, since $1$ has $1$ and itself as a factor!

Above, when we wrote all of the factors of $31$, you probably divided $31$ by $1$, $2$, $3$, $4$, and $5$ and then stopped because larger divisors would be greater than the square root. This strategy is called trial division, because we tried to divide by all the numbers we know. This strategy is great when we are in the mindset of making a list of all of the factors of a number, because if the number is not prime we want to make sure that we write down all of the factors. However, if we are just trying to see whether or not a number is prime, we can take a short cut that depends on the relationships between factors. Let’s investigate this relationship with an example and then apply it to our example.

We just showed that if $4$ is a factor of $N$, then $2$ must also be a factor of $N$. This works because $2$ is a factor of $4$. We can use similar equations to show if $A$ is a factor of $B$ and $B$ is a factor of $C$, then $A$ must also be a factor of $C$. Try the next question to see another example.

If we apply this idea to our example of finding whether or not $31$ is prime, remember that we divided by $1$, $2$, $3$, $4$, and $5$ in order to determine that $31$ is prime. But we could have skipped dividing by $4$ since we already know that $2$ is not a factor of $31$. Based on what we just learned, if $4$ is a factor of $31$, then $2$ would also have to be a factor of $31$, which we know isn’t true. Reversing this, we know that since $2$ isn’t a factor of $31$, we cannot have $4$ as a factor of $31$. We can now reduce the number of calculations we need in order to determine whether a number is prime.

The idea of using factors that we have already tested to determine whether a number is prime is also the main idea in one of the oldest algorithms for finding numbers, called the Sieve of Eratosthenes. Let’s use the sieve in the next example to find all of the prime numbers less than $40$.

Use the Sieve of Eratosthenes to find all of the prime numbers less than $40$.

The first step is to list out all of the numbers, beginning with $2$ and ending with $40$.

Next, we cross off all of the multiples of $2$ other than $2$ itself. These multiples of $2$ will have $2$ as a factor, and hence are not prime.

We now cross off all of the multiples of $3$ other than $3$ itself. Again, these multiples of $3$ are not prime.

We keep repeating this process with the next uncrossed number until we have no more multiples to cross off. So, we cross off the multiples of $5$, then $7$, and so forth. In the resulting chart, the numbers that are not crossed off must be the prime numbers.

A sieve is like a filter, and so you can think about this process as filtering out the multiples and keeping only the prime numbers.

Throughout this discussion, we have been decomposing numbers into their prime factors. This process is so common that we call it finding a prime factorization for a number. Let’s work through an example where we find a prime factorization.

Find the prime factorization of $132$.

We need to find the factors of $132$. Many people draw what is called a factor tree to help them keep track of the factors they are finding. A factor tree starts with the number we are factoring at the top, and then branches out into the factors below. We know that $132$ is an even number, and this means that $2$ must be a factor of this number. When we divide $132 \div 2$ we get $\answer [given]{66}$ so we record this in our factor tree by drawing two branches below $132$, one for $2$ and the other for $66$.

Now $2$ is a prime number, so we don’t need to factor it any more and its branch will end there. But $66$ can be factored as $6 \times \answer [given]{11}$, so we draw these two branches below the $66$.

We have that $11$ is prime, so we only need to factor $6$, which we know is $\answer [given]{2} \times 3$. We record these numbers on branches below the $6$.

Now that all of the branches end in prime numbers, we know that the original number is the product of all of these prime numbers. In other words, \[ 132 = 2 \times \answer [given]{2} \times 3 \times \answer [given]{11}. \] This is the prime factorization of $132$.

Unique factorization

Now that we have practiced finding a prime factorization, does it matter how we begin the process of factoring?

Let’s find another factor tree for $132$.

This time, let’s start by factoring $132$ as $6 \times \answer [given]{22}$. We will then need to factor both $6$ and $22$, and we see that \[ 6 = \answer [given]{2} \times 3 \] and \[ 22 = 2 \times \answer [given]{11}. \] These are now all prime numbers, so let’s write them on the branches in our factor tree starting with $132$ at the top.

Looking at the prime numbers at the ends of the branches, we see that \[ 132 = 2 \times 3 \times 2 \times \answer [given]{11} \] which can be rearranged using the commutative property to be \[ 132 = 2 \times 2 \times 3 \times 11. \]

We have now factored $132$ in two different ways and we got the same prime factorization in each case. This is an example of the Fundamental Theorem of Arithmetic.

The Fundamental Theorem of Arithmetic is important because it allows us to think about prime numbers as the instructions or building blocks for any positive integer. Because prime factorizations are unique, we have a specific recipe for building each number, and we can use this recipe to answer questions about the number. It’s a common technique for mathematicians who are asking questions about numbers to rephrase their questions in terms of prime numbers. Let’s see an example.

As we work through more problems about factors and multiples, watch out for instances where making a prime factorization will help you answer questions about numbers.