3 ms·
The product of primes plus one isn't always prime. For example: 3*5 + 1 = 16, not prime. Euclid's argument is that the product of some primes plus one is eith
by kazinator 4y ago
The product of primes plus one isn't always prime.
For example: 3*5 + 1 = 16, not prime.
Euclid's argument is that the product of some primes plus one is either prime or not; if it's prime, then it's an example of a prime that is not in the list. If it is not prime, then Euclid argues that the number's prime factors are not in the list.
To directly use Euclid's result to find a new prime number, we have to multiply some existing numbers together, add 1, and then factor that number. If it doesn't factor, then it is a new prime; otherwise its factors are new primes.
That seems constructive; all of the steps amount to a terminating algorithm that will give us at least one new prime.