Saturday, April 21, 2007

Proof that shows why we have an infinite number of primes

Say there are a finite number of primes so that we could list them out in a list:
p1, p2, p3, ....pn

now, lets create another number named m:
m = p1*p2*p3*....pn + 1

if m was a prime number it would have to be in the list

however, it can't be in the list because it is bigger than anything in the list so m isn't prime

m can't be divided by any number in the list (because it would leave a remainder of 1

all non-prime numbers can be divided by a prime number though as all non-prime numbers break down into primes

this is a contradiction so the assumption must be false and there must be an infinite number of primes

BRILLANT!

Observations about this proof:

1. If you had a list of all of the primes up to a point (2,3,5,7,...,n) and you multiplied them together and added 1, I believe you would always get a prime, but it wouldn't be the next prime. It would be much larger than the next prime.

2. if you have a list of primes (2,7) then m = 15 and 15 can be decomposed into primes 3 and 5 so this algorithm seems to only generate primes (for sure) if you have a complete list of all primes up to a point and then add 1.


Here is the next theorem To Prove:
For every positive integer n, there is a sequence of n consecutive positive integers containing no primes.

No comments: