Primes

Recall an integer $p$ is prime if $p>1$ and the only positive integers dividing $p$ are $1$ and $p$ itself. The first few primes are

$$2,3,5,7,11,13,17,19,... \ .$$

The primes form ``building blocks'' for the integers in some sense (made more precise by the Fundamental Theorem of Arithmetic and by Goldbach's conjecture). We will later see how primes occur in the encryption of information passed over the internet.

It has been known since the times of the Greeks that there are infinitely many primes. The following result is one of the oldest and best known results in mathematics!

Theorem 1.5.1 (Euclid's Second Theorem)   There are infinitely many primes.

proof: If $p_1,p_2,...,p_k$ denote a sequence of primes then $n=p_1p_2...p_k+1$ is not divisible by any of these primes. But every integer is divisible by some prime, so there is a prime not included in this set. Therefore, the set $\{p_1,...,p_k\}$ cannot be all the primes. If there is no finite list of primes then they must be infinite in number! $\Box$

In spite of their basic nature and importance, many questions about primes remain unknown.

Question: Given a ``random'' integer $n$ is there a ``fast'' method of determining if $n$ is a prime or not?

The answer depends on your definition of ``fast''. Basically, the answer is that there are several primality testing methods known and some work faster for certain types of integers (like those of the form $2^n\pm 1$) and for other types. We will return to this topic in §1.5.3 below.

In two letters to Euler dated 1742, Goldbach conjectured the following result.

Conjecture 1.5.2 (Goldbach conjectures)  

(a) If $n>5$ is any odd integer then $n$ is the sum of three primes (i.e., there exist three prime numbers $p_1,p_2,p_3$ such that $n=p_1+p_2+p_3$).

(b) If $n>2$ is any even integer then $n$ is the sum of two primes (i.e., there exist two prime numbers $p_1,p_2$ such that $n=p_1+p_2$).

Conjecture (a) was essentially solved by I. M. Vinogradov in 1937 [Va] but Conjecture (b), after over 250 years, is still unsolved.

Suppose the number of primes up to $N$ is denoted by $\pi(N)$. By Theorem 1.5.1, we know that as $N\rightarrow \infty$, $\pi(N)\rightarrow \infty$. No simple exact formula for $\pi(N)$ is known. It was guessed in the 1800's that $\pi(N)$ is about $N\over\ln(N)$.

More precisely, we have the following result.

Theorem 1.5.3 (prime number theorem)   For any choosen $\epsilon>0$ there is an $N_0(\epsilon)>1$ (which may be extremely large) such that, $(1-\epsilon){N\over \ln (N)} <\pi(N)<(1+\epsilon){N\over \ln(N)}$, for all $N>N_0(\epsilon)$.

The proof of this theorem goes beyond the scope of this book (see for example, Hardy and Wright [HW]). Unfortunately, no one knows for sure what a good estimate for what $N_0(\epsilon)$ is! One can re-interpret the result as stating that, for $x$ large, the probability an integer near $x$ is prime is about ${1\over \ln (x)}$.

In spite of the fact that there are infinitely many primes, the general problem of showing that there are infinitely many primes of a certain type is very hard. We give a couple of examples of this idea.

Conjecture 1.5.4 (twin primes conjecture)   There are infinitely many primes $p$ for which $p$ and $p+2$ are prime.

Examples include $11$ and $13$, $17$ and $19$, and many others.

Conjecture 1.5.5   There are infinitely many primes $p$ of the form $n^2+1$, for some integer $n$.

Examples include $5$, $17$ and many others.

Conjecture 1.5.6 (Mersenne prime conjecture)   There are infinitely many primes $p$ of the form $2^n-1$, for some integer $n$.

Examples include $7$, $31$ and some others.