Skip to main content

Chapter 3 Primes

Definition 3.0.1.

A natural number \(k\) is a proper divisor of an integer \(n\gt 1\) provided \(k\vert n\) and \(1\lt k\lt n.\)

Definition 3.0.2.

A prime is a natural number \(p\gt 1\) which has no proper divisors.

Figure 3.0.3. The first \(100\) prime numbers.

Notice that there are many pairs of primes \((p,p+2),\) like

\begin{equation*} (3, 5),(5, 7),(11, 13),(17, 19),(41, 43),...,(521, 523). \end{equation*}

We call these primes twin primes, and note one of the most famous open conjectures in number theory.

This conjecture was first proposed by Euclid sometime around 300 B.C.

Two other very famous conjectures in number theory concern the sum of two primes. In a letter to Euler in 1742, Christian Goldbach suggested the following conjectures.

In 1937, I.M. Vinogradov produced a proof of the Ternary Goldbach Conjecture for large integers 1 . Thus the question is settled for integers \(N,\)

\begin{equation*} N\gtrsim 3.33\cdot 10^{43000}. \end{equation*}

Unfortunately, this number is not quite small enough for computers to tackle the "small" integers that are left to check. But in 2013, Harald Helfgott proved that the result is true for \(N \gt 10^{27},\) a small enough bound so that the remaining cases could be checked. Thus Conjecture 3.0.6 is now a theorem due to Helfgott.

Vinogradov's original bound was \(N\geq 3^{3^{15}}\approx 3.25\cdot 10^{6846168}.\)

The most famous proven result in prime number theory is called the Prime Number Theorem. To state this we fist need some notation and a definition.

Convention 3.0.7.

Let \(f(x)\) and \(g(x)\) be two real valued positive functions. We write \(f(x) = O(g(x))\) and say "\(f(x)\) is big-oh of \(g(x)\)" provided there is a real number \(c_1 \gt 0\) such that for \(x\) large enough

\begin{equation*} f(x)\leq c_1g(x). \end{equation*}

We write \(f(x) = o(g(x))\) and say "\(f(x)\) is little-oh of \(g(x)\)" provided that

\begin{equation*} \lim_{x\rightarrow \infty}\frac{f(x)}{g(x)}=0. \end{equation*}

We say that \(f\) and \(g\) are asymptotic, written

\begin{equation*} f(x)\sim g(x) \end{equation*}

provided

\begin{equation*} \lim_{x\rightarrow\infty}\frac{f(x)}{g(x)}=1. \end{equation*}

Finally we say that \(f\) is of order \(g,\) written

\begin{equation*} f(x)\asymp g(x) \end{equation*}

provided there exist real numbers \(c_1,c_2\gt 0\) such that for \(x\) large enough we have

\begin{equation*} c_1g(x)\leq f(x)\leq c_2g(x). \end{equation*}

Definition 3.0.8.

Let \(x\geq 0\) be a real number. Denote by \(\pi(x)\) the number of primes less than \(x;\) we call \(\pi(x)\) the prime counting function.

This theorem was conjectured by Legendre and Gauss in the 1790's, but was not proven until well after that in 1896. In that year, the Prime Number Theorem was proven independently by both Hadamard and de la Vallée Poussin.