A One-Line Proof of the Infinitude of Primes

Re:A One-Line Proof of the Infinitude of Primes by mikeash on Tuesday November 15, 2016 @01:32PM (#12960793)

Depending on how much you're willing to assume and what exactly counts as "one line," it could be as simple as:

> One plus the product of all primes is itself prime, and larger than all primes.

This omits a bunch of stuff, but it seems like less than the linked paper.

[ Parent | on HN ]

Re:A One-Line Proof of the Infinitude of Primes by dllthomas on Tuesday November 15, 2016 @01:43PM (#12960917)

> One plus the product of all primes is itself prime

One plus the product of the first N primes is not necessarily prime. Consider 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509

[ Parent | on HN ]

Re:A One-Line Proof of the Infinitude of Primes by mikeash on Tuesday November 15, 2016 @01:49PM (#12960972)

How about: one plus the product of a list of primes has a prime factor not in the list.

[ Parent | on HN ]

Re:A One-Line Proof of the Infinitude of Primes by dllthomas on Tuesday November 15, 2016 @02:02PM (#12961109)

Yup, that works!

[ Parent | on HN ]

Re:A One-Line Proof of the Infinitude of Primes by mikeash on Tuesday November 15, 2016 @02:03PM (#12961120)

I like that version better anyway. Thanks for helping me improve it!

[ Parent | on HN ]

Re:A One-Line Proof of the Infinitude of Primes by jwatte on Tuesday November 15, 2016 @02:08PM (#12961157)

Yes! Because primes are infinite! The statement assumes limited primes. And, because it falsifies, it proves primes must be unlimited. I find this argument based on prime factors much simpler.

[ Parent | on HN ]

Re:A One-Line Proof of the Infinitude of Primes by dllthomas on Tuesday November 15, 2016 @08:27PM (#12963854)

I would have been fine with "would have to be prime"; I like the edit Mike suggested even better.

[ Parent | on HN ]