NTIC Introduction to Primes

🔗

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; if you don't think so, you can try the Prime Landing Game at the educational website Hoodamath and see how you do! 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?
xxxxxxxxxx

is_prime(6) # Is my number a prime?
Language:
Messages
Is it at least a power of a prime?
xxxxxxxxxx

is_prime_power(25) # Is my number a prime power?
Language:
Messages
List some primes for me!
xxxxxxxxxx

PR = prime_range(100) # What are all primes up to but not including 100?
print(PR)
Language:
Messages
List the first $n$ primes …
xxxxxxxxxx

PFN = primes_first_n(100) # What are the first 100 primes?
print(PFN)
Language:
Messages

Give me prime factors.

xxxxxxxxxx
 
# What are the prime factors of a number?
factor( 2 * 3 * (2*3+1) * (2*3*(2*3+1)+1) * (2*3*(2*3+1)*(2*3*(2*3+1)+1)+1) )

🔗

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?

xxxxxxxxxx
 
f(x)=x^2+x+41
@interact
def _(n=(0,[0..39])):
    pretty_print(html("Is $%s$ for $x=%s$, which is $%s$, a prime number?"%(f(x),n,f(n))))
    print(is_prime(f(n)))

🔗

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.

xxxxxxxxxx
 
f(x)=x^2+x+41
f(40)

xxxxxxxxxx
 
is_prime(f(40)),factor(1681)

🔗

In fact, we can prove that quite the opposite of what you might have thought with this example 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 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.

xxxxxxxxxx
 
g(x)=8*x^2-488*x+7243
for n in [0..30]:
    print(g(n),is_prime(g(n)))

🔗

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.

xxxxxxxxxx
 
h(x)=x^6+1091
for n in [0..3906]:
    if is_prime(h(n)):
        print((n,h(n)))

🔗

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.