Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

orkesruim40

orkesruim40

Open question

2022-08-17

Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?

Answer & Explanation

Porter Mata

Porter Mata

Beginner2022-08-18Added 18 answers

In fact Euclid's proof is thoroughly constructive: it gives an algorithm which, upon being given as input any finite set of prime numbers, outputs a prime number which is not in the set.
Max Macias

Max Macias

Beginner2022-08-19Added 3 answers

Euclid's theorem is intuitionistic. Given any finite set S of primes, their product plus one is not divisible by any of the primes and hence is divisible by some prime not in S. This gives a concrete upper bound on the n-th prime as well -- though of course it's astronomical.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school geometry

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?