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 is a prime iff and has no proper divisors.

For example, and are primes, and is not a prime ( ).

Theorem 6.5.2   Any natural number is a prime or a product of primes.

Proof. If is a prime then we are finished. If is not prime then there exists two natural numbers and different from and from such that . If both are prime, we are done. Otherwise, we repeat the argument either for or for 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.

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 . Now define the number . The natural number is not divisible by any of the (if would be divisible by any of the primes , then would be divisible by this prime...). Thus is a new'' prime. We can repeat this process infinitely many times.

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 , for natural , but not all the numbers of this form are primes. The general case of numbers of the form has been solved by Dedekind. This can be made more precise. The following argument of Erdös shows that the smallest prime satisfies . Let be an integer such that all numbers can be written as the product of the powers of the first primes. So any such number can be written

with . Now , so there are at most possible numbers less than . Hence , or . Hence . A much deeper result (which will not be proved in this course!) is the Prime Number Theorem, that .

Subsections

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