Definition 5.3.1.1.
An integer \(p \gt 1\) is prime if the only positive factors of \(p\) are \(1\) and \(p\text{.}\) A positive integer greater than 1 that is not prime is called composite
Subsection 5.3.1 Primes
Remark 5.3.1.2.
In later courses, we extend the notion of prime to all integers. For simplicity, in this course we restrict the prime versus composite distinction to integers greater than 1. Even in the extended notion, \(1\) is not prime.
Example 5.3.1.3. First primes.
The first few primes are
\begin{equation*}
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \dots.
\end{equation*}
As a stronger version of Example 3.2.1.2 we have:
Theorem 5.3.1.4. Fundamental Theorem of Arithmetic.
Every integer that is greater than \(1\) can be written uniquely as a prime or a product of two or more primes, where the primes are written in order of non-decreasing size.
Proof.
For a proof see, for example, An inductive proof of fundamental theorem of arithmetic by Kevin Buzzard.
1
wwwf.imperial.ac.uk/~buzzard/maths/research/notes/inductive_proof_of_fundamental_theorem_of_arithmetic.pdf
Example 5.3.1.5. Factorization.
\begin{align*}
100 \amp = 2 \cdot 2 \cdot 5 \cdot 5 = 2^25^2 \\
253 \amp = 11 \cdot 13 \\
7007 \amp = 7 \cdot 7 \cdot 11 \cdot 13 = 7^2 \cdot 11 \cdot 13 \\
{23498357349} \amp =3 \cdot 53 \cdot 397 \cdot {372263}
\end{align*}
The following Theorem says than if an integer is composite, it must have a “small” prime factor, where ``small’’ means less than or equal to the square root of the number.
Theorem 5.3.1.6.
Proof.
We prove the theorem by contradiction. Let \(n\) be composite. Then there are \(a\in\NN-\{1\}\) and \(b\in\NN-\{1\}\) such that \(n=a\cdot b\text{.}\) Suppose \(a>\sqrt{n}\) and \(b>\sqrt{n}\text{.}\) Then
\begin{align*}
a\cdot b \amp \gt \sqrt{n}\cdot\sqrt{n} \\
\amp =\left(\sqrt{n}\right)^2 \\
\amp =n
\end{align*}
which contradicts \(a\cdot b=n\text{.}\) So one of \(a\) and \(b\) must be less than or equal to \(\sqrt{n}\text{.}\) As the prime factors of \(a\) and \(b\) are less than or equal to \(a\) respectively \(b\text{,}\) we have that \(n\) must have a prime factor that is less than or equal to \(\sqrt{n}\text{.}\)
Theorem 5.3.1.6 can be used to prove primality of certain integers. The theorem says that if an integer is composite, then it must have a small prime factor. The contrapositive says that if an integer does not have a small prime factor, then it must be prime.
Example 5.3.1.7. Primality proof.
Prove that \(523\) is prime.
Answer.
Theorem 5.3.1.6 says that if \(523\) is composite, it will have a prime factor less than \(\sqrt{523}\text{.}\) Since \(\sqrt{523} \approx 22.9\text{,}\) it suffices to show that no prime less than \(22\) divides \(523\text{.}\) That means we need to check \(2, 3, 5, 7, 11, 13, 17, 19\text{.}\) A quick computation shows that
\begin{align*}
523 \bmod 2 \amp = 1 \\
523 \bmod 3 \amp = 1 \\
523 \bmod 5 \amp = 3 \\
523 \bmod 7 \amp = 5 \\
523 \bmod 11 \amp = 6 \\
523 \bmod 13 \amp = 3 \\
523 \bmod 17 \amp = 13 \\
523 \bmod 19 \amp = 10.
\end{align*}
Thus \(523\) is prime.
Example 5.3.1.8. Primality proof interactive.
We can use the Sieve of Eratosthenes to find the primes up to some bound. This is a simple, ancient algorithm for finding all prime numbers up to any given limit.
The sieve works by iteratively marking as composite (that is , not prime) the multiples of each prime, starting with the first prime number, \(2\text{.}\)
Explore the sieving process in Figure 5.3.1.9. Click on a number to have all its multiples marked by changing the field color to red and crossing them out. Numbers that you have clicked appear on green background. When there are no white fields left, the numbers in green fields are all the prime numbers up to 192.
First click on \(2\text{,}\) then click on the first number that remained white, which is \(3\) and so on. To illustrate the sieving better multiples are marked with a delay and different shades of red are used for multiples of different numbers.
Through sieving, we could enumerate the primes up to a bound \(N\text{.}\) This number is denoted \(\pi(N)\text{.}\) Only \(5.0848\%\) of the positive integers less than \({1000000000}\) are prime. See Table 5.3.1.10 for additional data. It looks like the frequency with which primes occur is diminishing. It might be reasonable to guess that eventually prime numbers become so rare that beyond a certain bound, they no longer occur. This is not the case, as was known to the Greeks over 2000 years ago. The first known proof is due to Euclid (c.~300 BC). See Theorem 5.3.1.11. It turns out, the proportion \(\frac{\pi(N)}{N}\) of integers up to \(N\) that are prime does decrease, but at an ever decreasing rate. If you are interested, you can read more about the Prime Number Theorem and its fascinating history on Wolfram Mathworld
2
mathworld.wolfram.com/PrimeNumberTheorem.html| bound \((N)\) | number of primes \(\pi(N)\) | percentage \((\frac{\pi(N)}{N} \% )\) |
| 10 | 4 | 40.0000 % |
| 100 | 25 | 25.0000% |
| 1000 | 168 | 16.8000% |
| 10000 | 1229 | 12.2900% |
| 100000 | 9592 | 9.5920% |
| 1000000 | 78498 | 7.8498% |
| 10000000 | 664579 | 6.6458% |
| 100000000 | 5761455 | 5.7615% |
| 1000000000 | 50847534 | 5.0848% |
Theorem 5.3.1.11. Infinitude of primes.
There are infinitely many primes.
Proof.
We use proof by contradiction. Suppose there are finitely many primes. Label them as \(p_1, p_2, \dots ,p_n\text{.}\) Consider the integer \(q = p_1 p_2 \dots p_n + 1\text{.}\) By Example 3.2.1.2, we have that \(q\) is prime or can be expressed as a product of two or more primes. Since \(q \bmod p_i = 1\) for \(i = 1, 2, \dots, n\text{,}\) we have that \(q\) is not divisible by any prime. Thus \(q\) is prime. This gives the desired contradiction since \(q\) is a prime that is not on our list. Therefore, there are infinitely many primes.
https://xkcd.com/622/) After somewhere around 40 hours, there’s no academic reason to go to the class. Only go for the hallucinations.
