Euclid's theorem

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Euclides

Euclid's theorem is an important theorem in number theory that states that there are infinitely many prime numbers.

There are numerous proofs of the theorem.

Euclid's proof

Euclid formulated the first proof in proposition 20 of book IX of his work Elements. A common adaptation of this original proof goes like this:

It takes an arbitrary but finite set of prime numbers p₁, p₂♪ p_nand is considered the product of all of them plus one, q=p₁p₂ ·· p_n+1. This number is obviously greater than 1 and different from all cousins p_i from the list. Number q can be a cousin or compound. If he's a cousin, we'll have a prime number that's not in the original set. If, on the contrary, it is composed, then there will be some factor. p that divides to q (q=p₁p₂ ·· p_n+1). Assuming that p is one of the p_i, it deduces then that p divides the difference q-p₁p₂ ·· p_n=1, but no prime number divides to 1, that is, it has come to an absurdity to assume that p is in the original set. The consequence is that the set chosen is not exhaustive, since there are prime numbers that do not belong to it, and this is independent of the finite set that is taken.

There are numerous proofs similar to this one, which are formulated as follows:

Kummer's reformulation

Suppose there is a finite number of prime numbers p₁ < p₂ < p₃ <... < p_r. Let N = p₁ p₂ p₃·...·p_r > 2. The integer N-1, being a product of primes, has a divisor p_i that is also a divisor of N; so p_i divides N - (N-1) = 1. This is absurd, so that there must be infinitely many prime numbers.

Hermite Demonstration

Let n=1, 2, 3,... and q_n be the smallest prime factor of n! + 1 for each n. Since q_n has to be greater than n, it follows that this sequence contains infinitely many distinct elements, and therefore there are infinitely many prime numbers.

Stieltjes Demonstration

Suppose there are a finite number of prime numbers. Let Q be the product of all prime numbers, and let m and n be two positive integers with Q = mn.
We have that every prime number p divides either m or n, but not both, that is, m and n are prime to each other. So m+n cannot have any prime divisors, but since it is strictly greater than 1, it must be a prime number that does not divide Q: contradiction.

Other demos

Goldbach's Proof (1730)

This demonstration is based on Fermat numbers, that is, the numbers in the form: $F_{n} = 2^{2^n} + 1$ .

Lema: Two different Fermat numbers F_m and F_n They're cousins to each other.

(Goldbach, 1730)

For each Fermat number F_n, choose a prime divisor p_n. Since the Fermat numbers are mutually prime, we know that any two primes p_m and p_n are distinct. Thus, there is at least one prime number p_n for every Fermat number F_n, that is, at least one prime number for every integer n.

This proof is also valid if we take another infinite sequence of natural numbers that are prime to each other, such as the Sylvester sequence.

Euler's proof (1737)

In a 1737 paper entitled Variae observationes circa infinite series Euler gave another proof. He deduced the following formula:

{displaystyle 1+{frac {1}{2}}+{frac {1}{3}}+{frac {1}{4}}+{frac {1}{5}}+cdots ={frac {2cdot 3cdot 5cdot 7cdot 11cdot 13cdots }{1cdot 2cdot 4cdot 6cdot 10cdot 12cdots }}}

where the first expression is the harmonic series and "the numerator on the right is the product of all the prime numbers and the denominator is the product of all the numbers less than one unit to the prime numbers".

As the harmonic series diverges, so does the expression on the right, so the number of factors, the number of prime numbers, must be infinite.

Euler's proof

Let Q be the product of all the primes. Let φ(n) be the Euler function φ defined as the number of integers less than n and coprime with it. Then φ(Q) is equal to the product of the numbers that result from subtracting 1 from each of the prime numbers, that is,

φ(Q) = (2-1)·(3-1)·(5-1)·(7-1)·(11-1)·... = 1·2·4·6·10·...

One of the integers coprime with Q is 1. Still, there is at least one other integer in the interval [2,Q] that has no common factor with Q. That integer can't have any prime factors, because they're all in Q, so it must be equal to 1, leading to a contradiction.

Furstenberg's topological proof (1955)

Define a topology on the set of integers using arithmetic progressions (from −∞ to +∞). This generates a topological space. For each number p, let A_p be the set of all multiples of p. A_p is closed, because its complement is the union of all other arithmetic progressions with difference p. Now, let A be the union of the sequences A_p. If there is a finite number of prime numbers, then A is a finite union of closed sets, and therefore A is closed. However, all integers except -1 and 1 are multiples of some prime number, so the complement of A is {-1, 1} which is not open. This shows that A is not a finite union and that there are infinitely many primes.

Contenido relacionado

Más resultados...