Namespaces
Variants
Actions

Difference between revisions of "Euclidean prime number theorem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
Line 1: Line 1:
 +
{{TEX|done}}
 
The set of prime numbers is infinite (Euclid's Elements, Book IX, Prop. 20). The [[Chebyshev theorems on prime numbers|Chebyshev theorems on prime numbers]] and the asymptotic law of the [[Distribution of prime numbers|distribution of prime numbers]] provide more precise information on the set of prime numbers in the series of natural numbers.
 
The set of prime numbers is infinite (Euclid's Elements, Book IX, Prop. 20). The [[Chebyshev theorems on prime numbers|Chebyshev theorems on prime numbers]] and the asymptotic law of the [[Distribution of prime numbers|distribution of prime numbers]] provide more precise information on the set of prime numbers in the series of natural numbers.
  
Line 4: Line 5:
  
 
====Comments====
 
====Comments====
The proof of the Euclidean theorem is simple. Suppose there exist only finitely many prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363601.png" />. Consider the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363602.png" />. Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363603.png" /> it must be divisible by a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363604.png" />, which equals some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363605.png" /> due to the finiteness of the amount of prime numbers. Hence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363606.png" /> divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363607.png" />, and thus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036360/e0363608.png" /> divides 1. This contradiction shows that there must be infinitely many prime numbers.
+
The proof of the Euclidean theorem is simple. Suppose there exist only finitely many prime numbers $p_1,\ldots,p_k$. Consider the number $N=p_1\ldots p_k+1$. Since $N>1$ it must be divisible by a prime number $p$, which equals some $p_i$ due to the finiteness of the amount of prime numbers. Hence $p=p_i$ divides $N=p_1\ldots p_i\ldots p_k+1$, and thus $p_i$ divides 1. This contradiction shows that there must be infinitely many prime numbers.

Revision as of 15:50, 17 April 2014

The set of prime numbers is infinite (Euclid's Elements, Book IX, Prop. 20). The Chebyshev theorems on prime numbers and the asymptotic law of the distribution of prime numbers provide more precise information on the set of prime numbers in the series of natural numbers.


Comments

The proof of the Euclidean theorem is simple. Suppose there exist only finitely many prime numbers $p_1,\ldots,p_k$. Consider the number $N=p_1\ldots p_k+1$. Since $N>1$ it must be divisible by a prime number $p$, which equals some $p_i$ due to the finiteness of the amount of prime numbers. Hence $p=p_i$ divides $N=p_1\ldots p_i\ldots p_k+1$, and thus $p_i$ divides 1. This contradiction shows that there must be infinitely many prime numbers.

How to Cite This Entry:
Euclidean prime number theorem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Euclidean_prime_number_theorem&oldid=31821
This article was adapted from an original article by S.M. Voronin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article