Prime Numbers

Definition 6.5.1   A natural number $p$ is a prime iff $p > 1$ and $p$ has no proper divisors.

For example, $13$ and $91$ are primes, and $171$ is not a prime ( $171=9 \cdot 19$).

Theorem 6.5.2   Any natural number $n > 1$ is a prime or a product of primes.

Proof. If $n$ is a prime then we are finished. If $n$ is not prime then there exists two natural numbers $n_1$ and $n_2$ different from $n$ and from $1$ such that $n = n_1 \cdot n_2$. If both are prime, we are done. Otherwise, we repeat the argument either for $n_1$ or for $n_2$ or for both; as a proper divisor of a natural number is smaller than this number, we deal here with decreasing sequences of natural numbers; as a decreasing sequence of natural numbers becomes stationary at some step, the process stops. $\qedsymbol$

Theorem 6.5.3 (Euclid)   There are infinitely many primes.

Proof. Assume that there exist only a finite number of primes and denote them by $p_1, p_2, \dots, p_n$. Now define the number $N = p_1 p_2 \dots p_n + 1$. The natural number $N$ is not divisible by any of the $p_i$ (if $N$ would be divisible by any of the primes $p_1, p_2, \dots, p_n$, then $1$ would be divisible by this prime...). Thus $N$ is a ``new'' prime. We can repeat this process infinitely many times. $\qedsymbol$

Note that we cannot build all the exisiting primes by that way. Actually, finding a process which enables us to buid all the primes is an open question. The ``smallest'' question, whether there exists an algebraic formula giving only primes is open too. For example, it si possible to prove that there exist infinitely mnay primes of the form $4k+1$, for natural $k$, but not all the numbers of this form are primes. The general case of numbers of the form $ak+b$ has been solved by Dedekind. This can be made more precise. The following argument of Erdös shows that the $k^{\text{th}}$ smallest prime $p_k$ satisfies $p_k \le 4^{k-1} + 1$. Let $M$ be an integer such that all numbers $\le M$ can be written as the product of the powers of the first $k$ primes. So any such number can be written

$$m^2 p_1^{i_1} p_2^{i_2} \dots p_k^{i_k},$$

with $i_1, \dots, i_k \in \{ 0, 1\}$. Now $m \le \sqrt{M}$, so there are at most $\sqrt{M}\, 2^k$ possible numbers less than $M$. Hence $M \le 2^k \sqrt{M}$, or $M \le 4^k$. Hence $p_{k+1} \le 4^k + 1$. A much deeper result (which will not be proved in this course!) is the Prime Number Theorem, that $p_k \sim k \log k$.