2.7: Theorems and Conjectures involving prime numbers

Last updated
Save as PDF

Page ID: 8979

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

We have proved that there are infinitely many primes. We have also proved that there are arbitrary large gaps between primes. The question that arises naturally here is the following: Can we estimate how many primes are there less than a given number? The theorem that answers this question is the prime number theorem. We denote by \(\pi(x)\) the number of primes less than a given positive number \(x\). Many mathematicians worked on this theorem and conjectured many estimates before Chebyshev finally stated that the estimate is \(x/log x\). The prime number theorem was finally proved in 1896 when Hadamard and Poussin produced independent proofs. Before stating the prime number theorem, we state and prove a lemma involving primes that will be used in the coming chapters.

Lemma

Let \(p\) be a prime and let \(m\in \mathbb{Z^+}\). Then the highest power of \(p\) dividing \(m!\) is \[\sum_{i=1}^\infty\left[\frac{m}{p^i}\right]\]

Among all the integers from 1 till \(m\), there are exactly \(\left[\frac{m}{p}\right]\) integers that are divisible by \(p\). These are \(p,2p,...,\left[\frac{m}{p}\right]p\). Similarly we see that there are \(\left[\frac{m}{p^i}\right]\) integers that are divisible by \(p^i\). As a result, the highest power of \(p\) dividing \(m!\) is

\[\sum_{i\geq 1}i\left\{\left[\frac{m}{p^i}\right]-\left[\frac{m}{p^{i+1}}\right]\right\}=\sum_{i\geq 1} \left[\frac{m}{p^i}\right]\]

The Prime Number Theorem

Let \(x>0\) then \[\pi(x)\sim x/log x\]

So this theorem says that you do not need to find all the primes less than \(x\) to find out their number, it will be enough to evaluate \(x/log x\) for large \(x\) to find an estimate for the number of primes. Notice that I mentioned that \(x\) has to be large enough to be able to use this estimate.

Several other theorems were proved concerning prime numbers. many great mathematicians approached problems that are related to primes. There are still many open problems of which we will mention some.

Twin Prime Conjecture

There are infinitely many pairs primes \(p\) and \(p+2\).

Goldbach’s Conjecture

Every even positive integer greater than 2 can be written as the sum of two primes.

The \(n^2+1\) Conjecture

There are infinitely many primes of the form \(n^2+1\), where \(n\) is a positive integer.

Polignac Conjecture

For every even number \(2n\) are there infinitely many pairs of consecutive primes which differ by \(2n\).

Opperman Conjecture

Is there always a prime between \(n^2\) and \((n+1)^2\)?

Contributors and Attributions

Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.