4 ms·

Is that proof not constructive? While you aren’t constructing the sequence of all primes, you are constructing some infinite set of primes to prove that there a

• DavidSJ 7y ago
  I doesn’t construct only primes. If p1, p2, ..., pn are prime, then p1p2...pn + 1 is not divisible by any of them, but it may not be prime itself.
  • a1369209993 7y ago
    Then you haven't proved a additional prime; you still need the (trivial[0]) step of breaking down 1+Πp into its one or more prime factors. And then you've constructed a (or several) prime not in the original set. 0: Trivial in the logical sense (try every number up to √(1+Πp)), but computationally impractical, thus left as a exercise for the reader.
    • thaumasiotes 7y ago
      You don't need that; you can proceed purely through generalities. 1. 1+Πp is congruent to 1 (mod p) for every prime p. 2. This conflicts with the definition of "prime number"; all composite numbers must be congruent to 0 (mod p) for some prime p. Only the empty product can be congruent to 1 (mod p) for every p. This is already sufficient to prove that the number of primes is not finite -- we derived a contradiction from that premise without demonstrating any additional primes. (Note that -- within the proof, where we've assumed a finite list of primes -- it's easy to show that 1+Πp is itself prime (since it has no prime divisors less than itself). You can then declare a contradiction with the premise, as it isn't in the original list. However, you can only show that it's prime by using the earlier contradiction, so while this step makes the proof more intuitive, it isn't actually necessary.)