Definition 7.3.1.
A prime number is a whole number that has exactly two factors; namely \(1\) and itself. If a natural number \(n\) is not prime, and not \(1\text{,}\) we say that \(n\) is composite.
Section 7.3 Prime Numbers
Prime numbers are the multiplicative building blocks of all whole numbers. In fact, we will see that every whole number can be decomposed into a product of (maybe repeated) prime numbers in exactly one way. Let’s define a prime number first:
It’s worth noting here that using this definition, \(1\) is not a prime number. Most mathematicians decided to follow this convention since \(1\) behaves quite differently to other prime numbers, and therefore to avoid frequently talking about \(1\) as a special case for various results, it was more convenient to exclude \(1\) from the list of prime numbers.
Subsection 7.3.1 Finding Prime Numbers
Let’s try and come up with a list of all prime numbers less than \(100\text{.}\) We could do this for all primes below any number, but we choose 100 for space reasons.
Let’s list all numbers up to 100, and we’ll cross off any numbers that we determine are not prime (so are composite, or the number \(1\)).
INSERT PIC OF NUMBERS FROM 1 TO 100
We’ll cross off \(1\) since we know that it doesn’t have exactly two factors; its only factor is itself. So now we know that the next largest number, \(2\text{,}\) must be prime since it has \(1\) and itself as a factor, and there are no other numbers smaller than \(2\text{.}\) So we circle \(2\) and cross off all numbers that have \(2\) as a factor.
INSERT UPDATED PIC
Now we can go to the smallest number that remains, \(3\text{,}\) and circle that since it must be prime; 2 is not a factor and there are no smaller prime numbers. Like before we circle \(3\) and cross off all other multiples of \(3\text{:}\)
INSERT UPDATED PIC
We can continue this process until all numbers are either circled or crossed off. Before looking below, try this yourself and check that you get the same list of primes as below:
INSERT UPDATED PIC
This process is very old, and in fact is called the sieve of Eratosthenes, after the Greek mathematician Eratosthenes of Cyrene, of whom this method is attributed to.
Checkpoint 7.3.3.
We found a list of prime numbers less than 100. Let’s see if we notice some patterns about primes by doing the same for numbers less than, say, 500.
-
Make a table of all numbers up to 500. You can probably search one online and print it off if that makes it easier.
-
Perform the sieve as above. It will take a bit longer, but it will be the exact same process.
-
What can you say about the amount of smaller prime numbers compared to the number of larger (at least closer to 500) prime numbers? Why do you think this is the case?
-
On the same chart, highlight all multiples of 6. What can you say about how prime numbers relate to multiples of 6? Formulate your conjectures in terms of remainders.
-
Try and prove the conjecture you made in the previous part.
Hint.
SECTION ON OTHER SIEVES? ON ALGORITHMIC COMPLEXITY? ON SEGMENTED SIEVES?
Subsection 7.3.2 How Many Prime Numbers Exist
Looking at the sieve above, it looks like prime numbers get more "rare" the higher up we go. So a good question to ask is whether we eventually "run out" of prime numbers, or whether there are infinitely many. Let’s explore this idea a little bit:
First, we need a small result to help us out. In math, we call a small result that helps us justify a larger result a lemma.
Lemma 7.3.4.
Let \(a_1,a_2 \ldots a_n \in \mathbb{N}\) be \(n\) numbers, and let \(a_* = a_1 \times a_2 \times \ldots \times a_n\text{.}\) Then for each \(a_i\) from \(a_1\) to \(a_n\) we have that \(a_i \nmid (a_*+1)\text{.}\)
Proof.
Left as an exercise.
Example 7.3.5.
-
Let’s make a new number by multiplying all numbers in \(A\) and then adding \(1:\text{,}\) say \(a=2 \times 3+1=7\)
-
By Lemma 7.3.4 we know that \(2 \nmid 7\) and \(3 \nmid 7\) (although this is pretty obvious anyway). So \(a\) is not divisible by any prime numbers in our set \(A\text{.}\) This means that \(a\) is either prime itself, or a product of other primes that aren’t already in \(A\text{.}\) In this case \(a=7\) is prime.
-
We now redefine \(A\) to include our new prime (or primes if \(a\) had other prime factors.) So in this case now \(A:=A \cup \{7\} = \{2,3\} \cup \{7\} = \{2,3,7\}\text{.}\)
-
We then repeat the procedure with the new \(A\) to obtain \(a=2\times 3\times 7+1 = 43\text{,}\) which itself is prime, so we include it in our set as well; \(A=\{2,3,7,43\}\text{.}\)
-
Let’s do this again: now \(a=2\times 3 \times 7 \times 43+1 = 1807\text{.}\) You can check that \(1807=13 \times 139\) which are both prime, so we can add \(13\) and \(39 \) to our set: \(A=\{2,3,7,13,39,43\}\text{.}\)
-
We can continue this process, and at each step we will form a number \(a\) that has no numbers in \(A\) as a factor, so we will be able to add at least one more prime number (either \(a\) itself if it is prime, or the prime factors of \(a\) if it is not) to our set.
-
As our set grows by at least one number every iteration of this process, we know we can always include at least one more prime number in our set. So we will never run out of prime numbers, and thus there are infinitely many prime numbers.
This exercise shows such an important result, that there are infinitely many prime numbers, that we should state this as a theorem:
Theorem 7.3.6.
There are infinitely many prime numbers
Some good questions come out of the previous exercise: first, will this list eventually include all prime numbers? Secondly, if we have a large number (like \(1807\) or even bigger,) how can we determine if this number has any prime factors? The second question we will answer in the next subsection of this section.
Checkpoint 7.3.7.
Hint.
Subsection 7.3.3 How To Determine If a Number is Prime
Think about a number like \(72\text{.}\) We can factor \(72\) into the product of two numbers in many ways, and we will list them all now.
\begin{equation*}
1 \times 72
\end{equation*}
\begin{equation*}
2 \times 36
\end{equation*}
\begin{equation*}
3 \times 24
\end{equation*}
\begin{equation*}
4 \times 18
\end{equation*}
\begin{equation*}
6 \times 12
\end{equation*}
\begin{equation*}
8 \times 9
\end{equation*}
Later, we will be very careful and learn how to check that these are all of the possible ways of factoring 72 into two numbers. But it is not too hard to check in this case (do you see how to do this?) Let’s plot these pairs on a number line to see if we notice something:
INSERT PIC OF A NUMBER LINE WITH EACH PAIR OF FACTORS OF 72 PLOTTED
It looks like the paris are approaching some point, let’s call it \(P\) between 8 and 9, plotted above, and that there is always one number of the pair that’s greater than \(P\text{,}\) and one that is less than \(P\text{.}\)
Let’s try the same process with another number, say \(100\text{,}\) and see if we can conjecture what this point \(P\) is mathematically:
Checkpoint 7.3.8.
-
Write down all possible factorizations of \(100\) into two factors. The factors do not have to be different numbers.
-
Graph these pairs of factors on a number line as above.
-
Can you determine the point \(P\) in this case? Can you give a mathematical meaning to this point, as it relates to \(100\text{?}\)
-
Conjecture what the meaning of point \(P\) is in the previous example.
From the exercise above, factoring any number \(n\) into two factors, it looks like our factorizations approach the positive square root of \(n\) (usually written \(\sqrt{n}\)). In a later section we will explore square roots, and other roots, in more detail. The key observation here is that in any pair of factors of \(n\text{,}\) one factor is always greater than or equal to \(\sqrt{n}\) and the other factor is less than or equal to \(\sqrt{n}\text{.}\) Let’s write this as a lemma:
Lemma 7.3.9.
Let \(n \in \mathbb{N}\text{.}\) If \(n=a\times b\) for some \(a,b \in \mathbb{N}\) where, say, \(a \geq b\text{,}\) then \(a \geq \sqrt{n}\) and \(b \leq \sqrt{n}\text{.}\)
Proof.
We are going to show this result is true using a proof by contradiction. As in part 3 of Subsection 1.2.2, we are going to pretend that there is a counterexample to our conditional statement (that is, the only situation where \(P \to Q\) is false; when \(P\) is true and \(Q\) is false.) We will show that if we are in this case, then mathematics "breaks" and we end up with something that is never true. This means that there are no counterexamples to our statement, so it must always be true. In our case, we will end up with showing that \(n > n\text{,}\) which is always false; of course, no number is strictly greater than itself!. The idea will be that if we multiply two number bigger than \(\sqrt{n}\) together, we must get a number bigger than \(n\text{.}\)
Assuming that the if-part is true, let \(n=ab\) be a factorization of \(n\) into two factors, where \(a \geq b\text{.}\) Let’s also assume that the then-part is false; that either both
-
\(a,b > \sqrt{n}\) or
-
\(a,b < \sqrt{n}\text{.}\)
There are two cases here. We will do the first case, and leave the second case as an exercise for you.
By the definition of a square root, we can write
\begin{equation*}
n = (\sqrt{n})(\sqrt{n})\text{.}
\end{equation*}
Since we’re assuming \(a > \sqrt{n}\text{,}\) if we replace one of the \(\sqrt{n}\) in the first expression with \(a\) we will obtain a larger product, so
\begin{equation*}
n = (\sqrt{n})(\sqrt{n}) > a(\sqrt{n}) \text{.}
\end{equation*}
Similarly, we’re also assuming \(b > \sqrt{n}\text{,}\) if we replace the other \(\sqrt{n}\) in the new expression with \(b\) we will obtain a larger product, so
\begin{equation*}
n = (\sqrt{n})(\sqrt{n}) > a(\sqrt{n}) > ab \text{.}
\end{equation*}
But we know that \(n=ab\) so we can replace the \(ab\) on the right hand side by \(n\text{.}\) So
\begin{equation*}
n = (\sqrt{n})(\sqrt{n}) > a(\sqrt{n}) > ab = n.
\end{equation*}
So if we look at the (in)equation above, we have just showed that \(n > n\text{.}\) Since this is never true, then there are no counterexamples to our original statement (at least in the first case).
The case where we assume that \(a,b < \sqrt{n}\) is very similar, and is left as an exercise to you. See if you can modify the case above to be a proof for this case.
Combining the two cases, we know that there are no counterexamples to our conditional statement, so it is always true.
We can use the idea above to help us, somewhat efficiently, determine if a number is composite. Indeed, if \(n\) is a composite number, it must have a pair of factors \(1 < a,b < n\) (and say that \(a \geq b\)) where \(n=ab\text{,}\) and by Lemma 7.3.9 it must be that \(b \leq \sqrt{n}\text{;}\) that is, every pair of factors of \(n\) has one of the factors that is no bigger than \(\sqrt{n}\text{.}\) So we can only worry about these factors, since the larger factors are paired with a smaller one.
We can do even better than checking if all numbers less than \(\sqrt{n}\) are factors of \(n\text{.}\) We’ll show that you only need to check whether the prime numbers less than \(\sqrt{n}\) are factors of \(n\text{.}\) First, we show that every composite number has at least one prime factor, and then we will show that the smallest non-unit (that is, not 1) factor of \(n\) is indeed a prime number.
Theorem 7.3.10.
Proof.
Similar to the previous proof, let’s show this by contradiction. We’ll pretend we have a counterexample (in fact the smallest counterexample), and show that something "breaks", so thus there must be no counterexamples. The contradiction we’ll have is that even though we picked the smallest counterexample, we’ll find one that’s smaller.
Let \(n\) be the smallest composite number (if-part true) that has no prime factors (then-part false). Since \(n\) is composite and has no prime factors, then \(n=ab\) for some composite numbers \(a,b\text{.}\) But all proper factors of a number are between \(1\) and \(n\) exclusive (that is \(1 < a,b < n\)). But since \(n\) has no prime factors, neither can \(a\) or \(b\text{,}\) since if \(a=pc\) for some prime number \(c\) then \(n=ab=(pc)b=p(cb)\text{,}\) and thus \(p\) is a factor of \(n\text{.}\) But this means that \(a\) is a smaller composite number than \(n\) with no prime factors, so \(n\) isn’t the smallest counterexample, even though we picked it to be. This means that there is no smallest counterexample, and thus no counterexample to our statement. So \(n\) must have at least one prime factor.
To show that the smallest factor of \(n\) is always a prime number, we do a very similar argument. We’ll leave it as an exercise, but we state the theorem.
Theorem 7.3.11.
Proof.
Left as an exercise.
Hint.
Putting this all together, we know that if a number \(n\) is composite then there is a prime number \(p \leq \sqrt{n}\) such that \(p \mid n.\) So to check that \(n\) is composite, all we need to do is check if each prime number up to \(\sqrt{n}\) is a factor of \(n\text{.}\) It’s more common to talk about testing if a number *isn’t* composite, so we will phrase the test below in that language:
Teat For Primality.
A number \(n \in \mathbb{N}\) where \(n \geq 2\) is prime exactly when it has no prime factors \(p \leq \sqrt{n}\text{.}\) We can test for primality using this following steps:
1. Determine the largest prime number \(p_* \leq \sqrt{n}\text{.}\)
2. For each prime number \(p \leq p_*\text{,}\) determine if \(p \mid n\text{.}\) If you find such a prime \(p\text{,}\) stop. Then \(n\) is composite. Otherwise go to the next step.
3. Congratulations! Your number \(n\) is prime!
Let’s see this test in action.
Example 7.3.12.
Determine if the number \(403\) is prime.
Solution.
First, we find the largest prime \(p_* \leq \sqrt{n}\text{.}\) If we have access to a calculator, we know that \(\sqrt{403} \approx 20\text{.}\) But if we do not, we can square primes and "sandwich" 403 between these squares. We know that \(19^2=361\) and the subsequent prime \(23^2=529\text{.}\) So this means that \(19 \leq \sqrt{403} \leq 23\text{,}\) and \(19\) is the largest prime that is less than or equal to \(\sqrt{403}\text{.}\)
We now test the divisibility of each prime up to \(19\) into \(403\text{.}\) If none of these primes are a factor of \(403\) then by our test for primality, \(403\) is prime. We will do each prime individually, and when we have a divisibility rule to help us, we will use that.
7: By division, we know that \(403 \div 7 = 57R4\text{.}\) Since we have a non-zero remainder we know \(7 \nmid 403\text{.}\)
13: By division, we know that \(403 \div 13 = 31\text{.}\) So indeed \(13 \mid 403\) and \(403=13 \times 31\text{.}\) We have found a prime factor of \(403\) and thus by our test for primality, \(403\) is not prime (and we have a factorization of it too!)
Note that once we find a prime that divides our number \(n\text{,}\) we do not need to test the other primes; we already know that \(n\) is composite.
Example 7.3.13.
Determine if \(293\) is prime.
Solution.
We need to find the greatest prime less than or equal to \(\sqrt{293}\text{.}\) Without a calculator, we can bound \(\sqrt{293}\) between two consecutive primes, or put another way, bound \(293\) between two squares od primes.
We know that \(17^2=289\) and \(19^2=361\) so \(17 \leq \sqrt{293} \leq 19\text{,}\) and our \(p_*=17\)
7: By division, we know that \(293 \div 7 = 41R6\text{.}\) Since we have a non-zero remainder, we know \(7 /nmid 293\text{.}\)
13: By division we know that \(293 \div 13 = 22R7\text{.}\) Since we have a non-zero remainder, we know \(13 \nmid 293\text{.}\)
17: By division we know that \(293 \div 17 = 17R4\text{.}\) Since we have a non-zero remainder we know that \(17 \nmid 293\text{.}\)
We have checked the divisibility of all primes up to and including \(17\text{.}\) Since we have found that none are factors of \(293\) our test for primality guarantees us that \(293\) is prime.
