Misunderstanding Euclid's argument
A common flawed presentation of Euclid's proof of the infinitude of primes is as follows:
Assume there are only a finite number of primes p 1 , p 2 , … , p n . Let N be the product of all of those primes, add to it 1 and you get a new prime number since it isn't divisible by any of the primes we listed at first. Contradiction! ⇒ ⇐ Therefore, there is an infinite number of primes.
Let q 1 , q 2 , q 3 , … be the list of all primes (in ascending order). Your mission is to find the smallest value of q 1 q 2 q 3 … q n + 1 that is not a prime.
The answer is 30031.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
I have edited your question for clarity, given the number of comments / disputes.
For example, you did not clarify that p 1 , p 2 , … must be the list of all the primes in order.
Log in to reply
I still find the wording a bit ambiguous, (I tried 4 and 1 5 as answers before trying 3 0 0 3 1 ). Perhaps something like "Let q 1 , q 2 , . . . . , q n be the list of the first n primes in ascending order" would make it crystal clear.
This is a great 'gateway' question for learning about primes. I can picture it on the Brilliant facebook page. :)
Absolutely fantastic problem. I loved solving this. :D
Log in to reply
Glad you liked it! :-)
is there a method to find 30031 or is it just by trial
Log in to reply
Just by trial. It is mentioned in some books. If you remember this then it's quite good. For example, it is there in the book Elementary Number Theory by David M.Burton
how about (2x7)+1 which is 15? you did'nt say it must in order so my answer is valid
Log in to reply
Let q1,q2,q3,...,qn is list of ALL primes in ASCENDING ORDER Dont you see that ?
meticulous answer and a great question , I loved it
Excellant.I was also clubbed at first although having used the proof earlier. Actually should have unerstood that N+1 is either the prime next to p n or is divisible by a prime >p n.Thus it is proved. Brilliant,
Trail and error ? Please explain the detailed procedure. By what numerical methods you solved this ?
Could you reword the problem? It's not completely clear you need to input 30031 instead of 6(the number of primes you need to multiply).
If it's a true geometric series that doesn't stop then were not talking about primes anymore
But isn’t there a smaller answer where 3 x 5 x 7 + 1 = 106 which is not prime
Log in to reply
The product of primes needs to start with the first prime, namely 2 , so your example doesn't qualify.
Great proof. Just a little question: if Euclid proved that for the product of some primes plus 1, the prime factors of that number were not those initial primes, then it is proven that there are infinitely many primes, isn't it? I mean, you just have to assume that the product p1·p2·p3···pn contains every prime (thinking they are finite), so when you add 1 you know you will have a new number whose prime factors are not p1, or p2, or p3, etc. So there's a number that either has a different prime factor, or is itself a prime. In any case, you would have "found" a new prime number, so it is a contraction, and they're, indeed, proven to be infinite.
I didn't know this was the actual proof. I saw a variation once: Proof by contradiction Let q be any prime number Assume q is the largest prime Take q! And add 1 and call it n Then this number is not divisible by any natural number < n. So n must prime or a product of primes that are greater than n Which means q is not the largest prime. QED
This is a truly simple and elegant proof!
Technically, the smallest such N + 1 is 4, because you can assume that 3 is the only prime number. You should clarify the question.
We cannot assume 3 only, because int he question it is told that first we have to assume there are only finite number of primes from p1 to pn, In this we know that p1 is 2(first prime number). So if we take pn as 3, then p1 to pn will be (2,3). If we take pn as 11 (2,3,5,7,11)...etc...
No, N is a product of primes, thus your example is false since if you consider primes up to 3 you will get 2 ⋅ 3 + 1 = 6 + 1 = 7 which is a prime.
I don't think you understand the question. It doesn't allow for counter-factual assumptions. q 1 is 2, q 2 is 3, etc... You're mission is to find the least n such that..etc. etc.
2*7 = 14, 14 + 1 = 15 not prime. I am missing something here
2 isn't really prime get over it
N=3 is a product of primes, namely the prime 3 (one number still counts as a product). But my point is, the question doesn't say "primes up to p n ". It doesn't even say the primes have to be in order from least to greatest. Therefore, using N = 3 is valid.
Log in to reply
are you assuming 3 as a product in this context- 1*3? 1 is not a prime number at all...the first prime number is 2. Anyway, the question has been edited and you have to take the prime numbers in order.
Use any 4k+3 you want, it'll hurt you just the same
I do not see why the given presentation of the proof is flawed, it is correct. We find a number 30031 which is not divisible by any of the listed primes. And since the presumption was that they were all existing primes, that presumption must be false. If the finite list contains all primes, the number cannot be composite. The facts that there is no finite list of all primes, and that 30031=59×509 really is composite do not compromise this reasoning. No one claimed that this method would always generate a new prime from a finite subset of all primes!
Using numerical methods, one can find such number to be: 3 0 0 3 1 = 2 × 3 × 5 × 7 × 1 1 × 1 3 + 1 which isn't a prime since it can be factored as: 5 9 × 5 0 9 .
A side note: What Euclid actually proved is that if P is any finite set of primes (which might or might not be the first n primes) then the prime factors of ( ∏ P ) + 1 are not in P . See here for a constructive overview of the proof.