4 ms·
Oh, sorry, didn't realize that. It still doesn't work, though, as the example of 2 * 3 * 5 * 7 * 11 * 13 + 1 = 59 * 509 shows.
by cion 7y ago
Oh, sorry, didn't realize that. It still doesn't work, though, as the example of 2 * 3 * 5 * 7 * 11 * 13 + 1 = 59 * 509 shows.
- conanite 7y agoIt's a little bit more subtle. Assume that there is a finite number of primes, and P is the set of all primes p0, p1, p2... pn. If you multiply all these together and add 1, you have a number Q that's not divisible by any number in P. So P cannot be the set of all primes.
- michaelt 7y agoRight, but if you were testing N=13 as the highest prime, then (2 * 3 * 5 * 7 * 11 * 13) + 1 must either be prime itself, i.e. have no prime factors, or must have a prime factor greater than 13. And in either case, a prime greater than 13 exists - in your example, 59. This is Euclid's proof [1] and it's some 2300 years old. [1] https://en.wikipedia.org/wiki/Euclid%27s_theorem https://en.wikipedia.org/wiki/Euclid%27s_theorem