next up previous contents
Next: Uniqueness of prime factorisation Up: The classical sets of Previous: Complexity of Euclidean Algorithm   Contents


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

$\displaystyle 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$.

Subsections
next up previous contents
Next: Uniqueness of prime factorisation Up: The classical sets of Previous: Complexity of Euclidean Algorithm   Contents
root 2002-06-10