Chapter 6 Prime Time
Now it's time to introduce maybe the most important concept in the whole course. It's one you are almost certainly already pretty familiar with. That is the concept of prime numbers.
Although we'll take a somewhat traditional route to introduce them, consider what precedes this chapter. We attacked linear congruences as far as we could via the concept of ‘relatively prime’/‘coprime’. But the thought should be gnawing at us of whether there is something deeper than simply not sharing factors other than one; what are the factors that are (or are not) shared in the first place? As mathematicians, we always want to ask whether there is a simpler notion available, or one that explains more.
We will see the fruit of this for linear congruences in Section 6.5, using the most powerful tool in our arsenal, Theorem 6.3.2. But once we have unleashed the power of primes, we will see and use them everywhere, such as in Chapters 22 and 12. Examining them more closely will lead to us some of the deepest mathematics of the book in Chapters 21 and 25.
So let's get started!
Summary: Prime Time
We can't wait any longer! In this chapter we talk all about prime numbers.
First, we define prime and composite numbers in Definition 6.1.1 and Definition 6.1.2. There is a lot of Prime fun to be had trying to find formulas for primes, or using Sage to compute.
The foundational result enabling the rest of our usage of primes is Euclid's proof of Infinitude of Primes, and the Sieve of Eratosthenes is a practical way to use this knowledge.
We define prime factorization in Definition 6.3.1. Then the great theorem saying this is both always possible and unique is the Fundamental Theorem of Arithmetic. Some of the details of its proof are important on their own, such as Corollary 6.3.7.
The following section gives many formulas that come directly as First consequences of the FTA.
Finally, we make explicit the procedure for Converting to and from prime powers in solving congruences, along with several interesting examples such as Example 6.5.3 and Example 6.5.4.
In the Exercises, the ones that practice the conceptual basis of the Fundamental Theorem of Arithmetic are the best.