LearnMathOnline

A prime number is an integer \(p\) greater than \(1\) that has no positive integer divisors other than \(1\) and \(p\) itself. A composite number is an integer greater than \(1\) that is not a prime number.

All composites are product of some other integers, in particular some primes. We denote the set of prime numbers by \(\mathbb P\).

Proof. (Euclid, 300 BC) Suppose there are finite number of primes: \(p_1 < p_2 < \cdots < p_n\). Let \(x=1+p_1p_2\cdots p_n\). Note that \(x>p_n>1\) and \(x\) is not a prime by our hypothesis. Then \(x\) has a divisor, in particular a prime divisor, say \(p\). This prime \(p\) is one of \(p_1,p_2,\ldots,p_n\) and thus \(p\vert p_1p_2\cdots p_n\). Since also \(p\vert x\), \[p\vert (x-p_1p_2\cdots p_n)=1.\] It contradicts the fact that no prime divides \(1\). ◼

First let us define a function \(\pi\) by \(\pi(n)\) being the number of primes less than equal to \(n\). For example, \(\pi(1)=0,\; \pi(2)=1,\; \pi(10)=4,\;\pi(10^6)=78498\) and by the preceding theorem \(\displaystyle\lim_{n\to \infty} \pi(n)=\infty\). The following theorem gives an asymptotic estimate of \(\pi(n)\).

Theorem (The Prime Number Theorem). \(\pi(n) \approx n/\ln n\) for large \(n\), more formally, \(\pi(n) \sim n/\ln n\), i.e., \[\displaystyle\lim_{n\to \infty} \frac{\pi(n)}{n/\ln n}=1.\]

First two proofs of the PNT were independently given by Jacques Hadamard and Charles Jean de la Vallée-Poussin in 1896. The following are two interesting consequence of the PNT.

Proof.

By the PNT, for large \(n\), \(\pi(n) \approx n/\ln n\) which implies \(\pi(n)/n \approx 1/\ln n\).

Note that \(\pi(p_n)=n\). By the PNT \(n=\pi(p_n) \approx p_n/\ln(p_n)\) for large \(n\). Thus \(p_n \approx n \ln(p_n)\). The result follows as \(\ln(p_n) \approx \ln(n)\) for large \(n\) (proof skipped). ◼

For example, for \(n=10^6\), \(n\ln n\approx 13,815,510\) and \(p_n=15,485,863\).

Dirichlet function \(li\) is defined by \(li(n)=\displaystyle\int_2^n\frac{dt}{\ln t}\) which is also a good estimate of \(\pi(n)\).

Question. How to determine if a given integer \(n\) is prime? (primality test)

A naive way is to check if any integer from \(2\) to \(n-1\) divides \(n\). A little better way is to concentrate on prime numbers from \(2\) to \(n-1\). The following result gives a much more efficient test.

Theorem. If a positive integer \(n\) has no prime divisor \(p\leq \sqrt{n}\), then \(n\) is prime.

Proof. (contrapositive) Suppose \(n\) is not prime. Then \(n=ab\) for some integers \(a,b\) where \(a\leq b\). So \(a^2\leq ab=n\) and \(a\leq \sqrt{n}\). Now either \(a\) is prime or it has a prime divisor \( p< a\leq \sqrt{n}\). ◼

Example. For \(n=163\), primes \(p\leq \sqrt{n}\approx 12.8\) are \(p=2,3,5,7,11\). None of them divides \(163\). So \(163\) is prime.

Using the preceding theorem we can find all the primes less than or equal to a given positive integer \(n\) by the sieve of Eratosthenes:
Consider integers \(2,3,4,\ldots,n\). For each prime \(p\leq \sqrt{n}\), cross out \(2p,3p,4p,...\), all the multiples of \(p\) less than or equal to \(n\). The remaining integers from \(2\) to \(n\) would be all the primes less than or equal to \(n\).

Example. For \(n=30\), primes \(p\leq \sqrt{n}\approx 5.5\) are \(p=2,3,5\). For \(p=2\), cross out \(4,6,8,\ldots,30\). Similarly for \(p=3\), cross out \(6,9,12,\ldots,30\) and for \(p=5\), cross out \(10,15,20,25,30\). The remaining integers are \(2,3,5,7,11,13,17,19,23,29\) which are all the primes \(\leq 30\).

The \(n\)th Mersenne number is \(M_n:=2^n-1\) for \(n\geq 1\). It is named after French priest Marin Mersenne (1588 - 1648) who stated that \(M_p=2^p-1\) is prime for \(p=2,3,5,7,13,17,19,31,67,127,257\). In 1876 French mathematician Edouard Lucas proved that \(M_{127}\) is a prime but not \(M_{67}\). A prime of the form \(2^p-1\) for a prime \(p\) is called a Mersenne prime. The largest known prime number \(2^{77,232,917}-1\) is a Mersenne prime with 23,249,425 digits found by GIMPS (Great Internet Mersenne Prime Search) in 2017.

French mathematician Pierre de Fermat (1607 - 1665) communicated to Mersenne and claimed that integers of the form \(2^{2^n}+1\) are prime. The \(n\)th Fermat number is \(F_n:=2^{2^n}+1\) for \(n\geq 0\) and a Fermat number that is a prime is called a Fermat prime. \(F_0\), \(F_1\), \(F_2\), \(F_3\), and \(F_4\) are the only known Fermat primes. It is unknown whether there are infinitely many Fermat's prime.

Some Prime Conjectures:
In 1912 German mathematician Edmund Landau popularized four problems about primes.

Goldbach's conjecture: Every even integer greater than \(2\) can be written as the sum of two primes.

Twin prime conjecture: There are infinitely many primes \(p\) such that \(p + 2\) is also a prime.

Legendre's conjecture: There is a prime number between \(n^2\) and \((n + 1)^2\) for every positive integer \(n\).

Near-square prime conjecture: There are infinitely many primes of the form \(n^2 + 1\).

Prime Numbers