PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] Euclid's proof of the infinitude of primes (Proof)

If there were only a finite amount of primes then there would be some largest prime $ p$. However $ p!+1$ is not divisible by any number $ 1<n\leq p$, since $ p!$ is, so $ p!+1$ cannot be factored by the primes we already know, but every integer greater than one is divisible by at least one prime, so there must be some prime greater than $ p$ by which $ p!+1$ is divisible.

Actually Euclid did not use $ p!$ for his proof but stated that if there is a finite list $ p_1,\ldots,p_n$ of primes, then the number $ p_1\cdots p_n+1$ is not divisible by any of these primes and thus either prime and not in the list or divisible by a prime not in the list.



"Euclid's proof of the infinitude of primes" is owned by mathwizard.
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: integer, number, divisible, primes, finite
There are 6 references to this entry.

This is version 5 of Euclid's proof of the infinitude of primes, born on 2002-06-04, modified 2008-03-17.
Object id is 3036, canonical name is ProofThatThereAreInfinitelyManyPrimes.
Accessed 4898 times total.

Classification:
AMS MSC11A41 (Number theory :: Elementary number theory :: Primes)

Pending Errata and Addenda
1. Slight Grammar Error by neapol1s on 2008-07-07 12:02:05
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy
primorials, not factorials by CompositeFan on 2006-06-14 18:11:10
I thought that Euclid's proof involved multiplying consecutive primes, not consecutive integers. The numbers still get big but they're a little bit more manageable.
[ reply | up ]

Interact
post | correct | update request | add example | add (any)