Euclid's theorem

The Euclid's theorem states that there infinitely many prime numbers are. This theorem goes back to the Greek mathematician Euclid , who around 300 BC . AD in Alexandria lived. In his work The Elements he wrote: “There are more prime numbers than any given number of prime numbers” (Book IX, Proposition 20).

Proof of Euclid

In today's language, Euclid makes the following assertion:

Given a finite set of prime numbers. Then there is at least one other prime number that is not included in. ${\displaystyle M}$ ${\displaystyle p_{1},\ldots ,p_{n}.}$ ${\displaystyle p_{n+1},}$ ${\displaystyle M}$

For this purpose, Euclid forms the smallest multiple of all prime numbers (It is not important for the proof that the smallest multiple is; however, it is important that all previous prime numbers are divisors of .) Then he forms and distinguishes two cases: ${\displaystyle m}$ ${\displaystyle M.}$ ${\displaystyle m}$ ${\displaystyle m}$
${\displaystyle m\!+\!1}$

1. ${\displaystyle m\!+\!1=:p_{n+1}}$is prime, then is another prime number. ${\displaystyle p_{n+1}\not \in M}$
2. ${\displaystyle m\!+\!1}$is not a prime number, then has a prime divisor. Assuming that it would then be a divisor of It is, however, also a divisor of and therefore also has to be a divisor of the difference . ${\displaystyle m\!+\!1}$ ${\displaystyle q.}$ ${\displaystyle q=:p_{i}\in M,}$ ${\displaystyle q}$ ${\displaystyle m.}$ ${\displaystyle m\!+\!1,}$ ${\displaystyle (m\!+\!1)-m=1.}$

The proof also works without the case distinction:

None of the given prime divisors of is divisor of because otherwise it would also have to divide the difference , which is not possible for prime numbers, since they are by definition . But if you all the numbers thus also can decompose into prime factors, then it must have the pass, other primes. ${\displaystyle p_{i}}$ ${\displaystyle m}$ ${\displaystyle m\!+\!1,}$ ${\displaystyle p_{i}}$ ${\displaystyle (m\!+\!1)-m=1}$ ${\displaystyle >1}$
${\displaystyle >1,}$ ${\displaystyle m\!+\!1,}$ ${\displaystyle p_{1},\ldots ,p_{n}}$

In all cases, the procedure described leads to the discovery of at least one new prime number, regardless of the set of prime numbers with which the proof is started, as long as this set is finite. Euclid provided the proof with only three prime numbers, just as in other places in the work "The Elements" three objects in the current sense of "any number of objects, but a finite number" are used.

The fact that Euclid's theorem (not necessarily Euclid's proof of Euclid's theorem) is regarded as an almost classic example of a proof of contradiction probably comes from the formulation:

Claim:	There are infinitely many prime numbers.
Proof:	Suppose the set of prime numbers were finite (apart from the subjunctive, this assumption corresponds exactly to the starting point of Euclid's proof). One can always construct at least one prime that is not in the finite set. So what is assumed must be wrong.

application

The proof of Euclid's theorem shows a possibility of how at least one further prime number can be calculated from one or more given prime numbers (or only natural numbers ). To do this, one forms the product of these numbers and adds 1 to the product, i.e. ${\displaystyle p_{1},p_{2},\dotsc ,p_{r}}$ ${\displaystyle >1}$

${\displaystyle n:=p_{1}p_{2}\dotsm p_{r}+1=\prod _{i=1}^{r}p_{i}+1}$.

Because of there is a smallest divisor of . This is necessarily a prime number. Furthermore is coprime to and thus different from each of the given numbers . ${\displaystyle n>1}$ ${\displaystyle d>1}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle p_{i}}$

If one only considers sets of consecutive prime numbers, that is , and forms the numbers from them ${\displaystyle p_{1}=2,p_{2}=3,p_{3}=5,\dotsc }$

${\displaystyle P_{r}:=2\cdot 3\dotsm p_{r}+1=\prod _{i=1}^{r}p_{i}+1}$,

then the first five of these numbers turn out to be prime, the next five to be composite. For example is

${\displaystyle P_{6}=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509}$.

It is an open question whether these numbers include an infinite number of prime numbers, an infinite number of composite numbers, or both.

Examples

The numbers 2, 5 and 11 form a finite set of prime numbers. According to the above formula is calculated to ${\displaystyle n}$

${\displaystyle n=1+2\cdot 5\cdot 11=111=3\cdot 37}$.

Both 3 and 37 are further prime numbers. It can be seen from FIG. 3 that prime numbers can also be found which are not larger than the specified prime numbers.

The numbers 2, 3, 5, 7 and 11 form a finite set of prime numbers. According to the above formula is calculated to ${\displaystyle n}$

${\displaystyle n=P_{5}=1+2\cdot 3\cdot 5\cdot 7\cdot 11=2311}$,

which is another prime number. This shows that the result itself can be a prime number.

The numbers 23 and 89 form a finite set of numbers. According to the above formula results

${\displaystyle n=1+23\cdot 89=2048=2^{11}}$,

a number whose smallest divisor is the prime number 2 is smaller than the two given numbers. ${\displaystyle >1}$

Let the set of numbers be . The formula gives the number ${\displaystyle \{2^{16}\}=\{65536\}}$

${\displaystyle n=65536+1=65537}$,

whose smallest divisor is a prime number, namely the Fermat prime number . ${\displaystyle >1}$ ${\displaystyle F_{4}=65537}$

See also

• Prime # Largest known prime

Web links

Wikibooks: Proof of Euclid's Theorem  - In the proof archive on Wikibooks there are further proofs for the existence of infinitely many prime numbers.

• Video: Euclid's Theorem . University of Education Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19866 .

Individual evidence

1. Jump up ↑ The Elements, Book IX, Proposition 20
2. ↑ With and is . Is now a common divisor of and , so and , then is , therefore a divisor of 1. So is for . ${\displaystyle s:=n/d}$ ${\displaystyle t:=-(n-1)/p_{i}}$ ${\displaystyle sd+tp_{i}=1}$ ${\displaystyle c\in \mathbb {Z} }$ ${\displaystyle d}$ ${\displaystyle p_{i}}$ ${\displaystyle d=d^{\prime }c}$ ${\displaystyle p_{i}=p^{\prime }c}$ ${\displaystyle 1=sd^{\prime }c+tp^{\prime }c=(sd^{\prime }+tp^{\prime })\,c=1}$ ${\displaystyle c}$ ${\displaystyle \operatorname {ggT} (d,p_{i})=1}$ ${\displaystyle i=1,\dotsc ,r}$