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>1 is not prime, it is called composite.

🔗
The first few primes are 2,3,5,7,11,… That means 4,6,8,9,10,12… 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 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.

  • 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.

🔗
This example is due to Euler 1 . For this form of polynomial it is the best known 2 , 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!

See [E.4.26, Chapter 11] or [E.4.8, Section 1.8] for a connection to Remark 13.3.4.
See references in the previous footnote.

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 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.