3 ms·
I think it's actually fairly hard (or at least non-trivial) to come up with a non-constructive proof of the infinity of primes? For example, Euclid's classic p
by eru 3y ago
I think it's actually fairly hard (or at least non-trivial) to come up with a non-constructive proof of the infinity of primes?
For example, Euclid's classic proof (the one that goes 'multiply all the primes you know, add 1') is at least implicitly constructive, because you can factor that new number with a well-known algorithm to get at least one new prime.
- gowld 3y agoIt's a non-constructive proof. Saying "you could extend the proof to be constructive for a single n" doesn't make it a constructive proof for all n. Infinity is quite a bit bigger than 1.
- MoonlitKnight 3y agoEuclid's proof is constructive in that it describes a procedure which, given a list of primes, computes a prime not on that list. Or equivalently, given a number n it computes a prime > 1.
- eru 3y agoAre you familiar with induction?