Section 6.1 Introduction to Primes
Subsection 6.1.1 Definitions and examples
Definition 6.1.1.
A positive integer \(p\) greater than 1 is called prime if the only positive divisors of \(p\) are \(1\) and \(p\) itself.
Definition 6.1.2.
If an integer \(n\gt 1\) is not prime, it is called composite.
The first few primes are
\(2,3,5,7,11,\ldots\) That means
\(4,6,8,9,10,12\ldots\) are composite. But figuring out which numbers are prime is notoriously difficult, to the point that educational websites sometimes offer tricky games with this as the goal – try
Is This Prime^{ 1 } if you think you are good at it! Indeed, we will spend significant time later on the question of deciding primality, such as in
Chapter 12 and
Chapter 21. So below, we introduce a few Sage functions for exploring the primes.
Here are answers to questions you might have about primes that Sage could answer.
Subsection 6.1.2 Prime fun
Before getting to the serious material, let’s have a little fun to start us thinking along the lines of what’s to come. For instance, did you ever try to see if there was a formula for primes?
It looks like a simple polynomial can get the primes for us! Of course, I’m cheating a little, as the next two sets of commands show.
This example is due to Euler
^{ 2 }. For this form of polynomial it is the best known
^{ 3 }, but you may have thought (based on the scanty evidence of this one example) that one could eventually find a polynomial which just gives primes. Quite the opposite is true!
Fact 6.1.4.
There is no non-constant polynomial \(f(x)\) with integer coefficients such that \(f(x)\) is prime for all integers \(x\text{.}\)
Proof.
What is the reason no such polynomial can exist? It turns out to be directly related to our previous work on congruences. Namely, if \(f(a)=p\) for some \(a\text{,}\) then suppose \(b\equiv a\) (mod \(p\)). By well-definedness of addition and subtraction, we then have \(f(b)\equiv f(a)\) (mod \(p\)) as well (since \(f\) is a polynomial!), so
\begin{equation*}
f(b)\equiv f(a)\equiv p\equiv 0\text{ (mod }p)\text{, which implies }p\mid f(b)\text{.}
\end{equation*}
Since we assume \(f(b)\) is actually prime, then \(f(b)=p\) as well.
But then the problem arises that
\begin{equation*}
f(a)=f(a+np)=p\text{ for all }n\in \mathbb{Z}\text{,}
\end{equation*}
which contradicts the well-known calculus fact that all non-constant polynomials have \(\lim_{x\to\infty}f(x)= \infty\text{ or }-\infty\text{.}\) So \(f\) must be constant.
It might be a big surprise to some readers to see that limits and calculus can be used in number theory! It is nice to see it at such an early stage, but there will be more later, such as in Chapters
24 and
20.
There are other single-variable polynomials that do happen to generate a number of primes; an impressive one follows. Among other sites,
Mathworld^{ 4 } has lots and lots more information.
One can ask the opposite question of finding functions which do not make many primes. The same website mentions the following polynomial, which takes an astounding long time to generate even two primes.
Finally, it is an important (and, to me, somewhat frightening) fact that
Fact 6.1.4 is not true for
systems of
multivariate polynomials; that is, some such systems have only prime output for integer input. See e.g.
Wikipedia^{ 5 } for the astounding details, including a polynomial
inequality that generates only primes.
See references in the previous footnote.
mathworld.wolfram.com/Prime-GeneratingPolynomial.html
en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations