Euclid's theorem

Euclid's theorem

Euclid's theorem is a fundamental statement in number theory which asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.

Euclid's proof

Euclid offered the following proof published in his work Elements (Book IX, Proposition 20) and paraphrased here.

Take any finite list of prime numbers p_1, p_2, dots, p_n. This list will be shown not to contain all prime numbers, as follows:

Let "P" be the product of all the prime numbers: P=p_1cdot p_2cdots p_n. Let "q" = "P"+1: more than this product. Then, "q" is either prime or not.

If "q" is prime then the list is not exhaustive: "q" is not on it.

If "q" is not prime then some prime factor "p" divides "q". This factor "p" is not on our list: if it were, then it would divide "P" (since "P" is the product of every number on the list); but as we know, "p" divides "P"+1 = "q". Then "p" would have to divide the difference of the two numbers, which is ("P"+1) − "P" or just 1. But no prime number divides 1 so there would be a contradiction, and therefore "p" cannot be on the list. This means the list is not exhaustive.

This proves, for "any" finite list of prime numbers, there is a prime number not on the list. Therefore there must be infinitely many prime numbers.

Euler's proof

Another proof, by the Swiss mathematician Leonhard Euler, relies on the fundamental theorem of arithmetic: that every number has a unique prime factorization. If "P" is the set of all prime numbers, Euler wrote that:
prod_{pin P} frac{1}{1-1/p}=prod_{pin P} sum_{kgeq 0} frac{1}{p^k}=sum_nfrac{1}{n}.
The first equality is given by the formula for a geometric series in each term of the product. To show the second equality, distribute the product over the sum: in the result, every product of primes appears exactly once, so by the fundamental theorem of arithmetic, the sum is equal to the sum over all integers.

The sum on the right is the harmonic series, which diverges. So the product on the left must diverge also. Since each term of the product is finite, the number of terms must be infinite, so there is an infinite number of primes.

ee also

* Dirichlet's theorem on arithmetic progressions
* Prime number theorem

External links

*
* [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html Euclid's Elements, Book IX, Prop. 20] (Euclid's proof)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Euclid number — In mathematics, Euclid numbers are integers of the form E n = p n # + 1, where p n # is the primorial of p n which is the n th prime. They are named after the ancient Greek mathematician Euclid.It is sometimes falsely stated that Euclid s… …   Wikipedia

  • Euclid's Elements — (Greek: polytonic|Στοιχεῖα) is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria circa 300 BC. It comprises a collection of definitions, postulates (axioms), propositions… …   Wikipedia

  • Euclid's lemma — (Greek polytonic|λῆμμα ) is a generalization of Proposition 30 of Book VII of Euclid s Elements . The lemma states that:If a positive integer divides the product of two other positive integers, and the first and second integers are coprime, then… …   Wikipedia

  • theorem — (n.) 1550s, from M.Fr. théorème, from L.L. theorema, from Gk. theorema spectacle, speculation, in Euclid proposition to be proved, from theorein to consider (see THEORY (Cf. theory)) …   Etymology dictionary

  • Euclid — /yooh klid/, n. 1. fl. c300 B.C., Greek geometrician and educator at Alexandria. 2. a city in NE Ohio, near Cleveland. 59,999. * * * flourished с 300 BC, Alexandria, Egypt Greek mathematician of antiquity, known primarily for his highly… …   Universalium

  • Euclid — Infobox Scientist name = Euclid image width = caption = birth date = fl. 300 BC residence = Alexandria, Egypt ethnicity = Greek field = Mathematics known for = Euclid s Elements Euclid (Greek: . polytonic|Εὐκλείδης mdash; Eukleidēs), fl. 300 BC,… …   Wikipedia

  • Theorem — The Pythagorean theorem has at least 370 known proofs[1] In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements …   Wikipedia

  • Dirichlet's theorem on arithmetic progressions — In number theory, Dirichlet s theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n ≥ 0. In other… …   Wikipedia

  • Pythagorean theorem — See also: Pythagorean trigonometric identity The Pythagorean theorem: The sum of the areas of the two squares on the legs (a and b) equals the area of the square on the hypotenuse (c) …   Wikipedia

  • Pythagorean theorem — Geom. the theorem that the square of the hypotenuse of a right triangle is equal to the sum of the squares of the other two sides. [1905 10] * * * Rule relating the lengths of the sides of a right triangle. It says that the sum of the squares of… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”