As panic pointed out, the nonconstructive proof you outline is valid, but the constructive "proof" is fallacious. You could modify the standard proof to construct a new prime, but that wouldn't be the famous proof. The modification amounts to doing a bunch of extra work after you've already finished the proof.

It's still constructive, you just have to change a word. That you insist on dismissing the method entirely baffles me.

I'm sorry that I didn't remember it off the top of my head.

Factoring is not a huge burden compared to the earlier steps, and also not necessary a lot of the time, especially if your goal is to keep feeding the number back into the system to create numbers made out of new primes.

> Factoring is not a huge burden compared to the earlier steps

I agree with this. My point is just that it's not required for the proof, and usually isn't included -- so the proof is not constructive. You can extend it to be constructive in a very straightforward manner, but you don't have to and you usually don't.

The reason I'm calling this a nonconstructive proof is by analogy to the following proof, often given as an example of a nonconstructive proof:

Theorem: it is possible for an irrational number raised to an irrational power to result in a rational number.

0. For typographic convenience, let r = sqrt(2). r is known to be irrational.

1. r^r might or might not be rational -- who knows?

2a. If r^r is rational, the theorem is proved.

2b. If r^r is not rational, then (r^r)^r is an irrational number raised to an irrational power, but (r^r)^r = r^(r⋅r) = r^2 = 2, which is rational.

3. Therefore, there exists some pair a,b for which the following is true: (I) a and b are both irrational; (II) a^b is rational.

I don't see any way to consider this proof nonconstructive while considering the proof of the inifinitude of the primes that I've described as constructive. Do you?

This constructive version doesn't work, though. The "new prime" 2×3×5×7×11×13 + 1 actually equals 59×509.

All of its prime factors are in fact new primes though - the constructive proof just requires you to use the prime factors of all the primes multiplied together, plus one.

Right, sorry, I should have said it gives you a new prime (or more), not that it is a new prime.