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. Indeed, we will spend significant time later on this question, such as in Chapter 12 and Chapter 21. So below, we introduce a few Sage functions for this.

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.

Here's a little fun that starts us thinking along the lines of what's to come. Let's see whether we can generate some primes with a simple polynomial.

Of course, I'm cheating a little:

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\), then for any \(b\equiv a\) (mod \(p\)) we have \(f(b)\equiv f(a)\) (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{, or that }p\mid f(b)\; .\end{equation*} But the problem is that if \(f(b)\) is also prime for all such \(b\), then we have a polynomial which returns to height \(f(x)=p\) periodically, and hence \(\lim_{x\to\infty}f(x)\neq \pm \infty\), which is only possible if \(f\) is a constant polynomial.

This could be a big surprise – limits and calculus can be used in number theory! Even at this early stage, it is evident, but there will be more later, such as in Chapters 24 and 20.

The fact is not true for multivariate polynomials (see e.g. Wikipedia). Yikes!

A few more single-variable polynomials that do happen to generate a number of primes are below, though the second one takes a long time! Among other sites, Mathworld has lots and lots more information.