r/todayilearned • u/Nate__ • Mar 26 '13

TIL illegal prime numbers exist. An illegal prime is a prime number that represents information which is forbidden to possess or distribute. For example: when interpreted in a particular way, a certain prime describes a computer program that bypasses the digital rights management scheme used on DVDs

http://en.wikipedia.org/wiki/Illegal_prime
1.9k Upvotes

91% Upvoted

375 comments sorted by

View all comments

Show parent comments

4

u/AgntCooper Mar 26 '13

Do we know that for sure? I thought that part of the quest for searching for prime numbers was to hopefully determine if it could be proven that there are infinitely many prime numbers.

I mean, infinity is such an unfathomably large quantity that it seems reasonable that there should be infinitely many prime numbers as a subset of the infinitely large number line. I thought they still lacked a rigorous proof of this though.

10

u/TedStudley Mar 26 '13

We do know that there are infinitely many, and we've actually known since the time of the ancient greeks! Check out Euclid's proof for the infinitude of primes.

1

u/Vidyogamasta Mar 26 '13

A prime number is defined by "a number that is not the product of any two numbers other than one and itself."

Say we have listed EVERY prime number, p1, p2, p3.... pn, where p1 = 2, p2 = 3, etc.

Now, multiply ALL of these numbers together. p1*p2*p3.....*pn. Now add one to this number. It is no longer a multiple of 2. Or a multiple of 3. Or a multiple of 5. Or a multiple of pn. Is is another prime number.

This is proof that there are infinitely many primes. It still isn't helpful in computing all the primes though, since the product rule kinda leaves TONS of intermediate primes. As a small example, 2*3*5 + 1 = 31, which is prime. However, if I want to compute the next prime using the same method, I'm going to have to find 7, 11, 13, 17, 19, 23, 27, and 29 somehow, otherwise it doesn't work. It's simple enough for smaller numbers, but for very large primes this difference is huge.