Skip to main content

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 would offer tricky games with this as the goal! 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.

  • Is a given number prime?

  • Is it at least a power of a prime?

  • List some primes for me!

  • List the first \(n\) primes …

  • Give me prime factors.

Sage note 6.1.3. Making comments.

Sometimes we might want to have notes about the code included without being actual code. In the Python language, such comments must come after # signs.

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.

In fact, we can prove that quite the opposite of what you might have thought with this example is true.

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 for any \(b\equiv a\) (mod \(p\)) we have \(f(b)\equiv f(a)\) (mod \(p\)) (by well-definedness of addition and subtraction) as well, 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 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 for the astounding details, including a polynomial inequality that generates only primes.