Are there an infinite number of primes or a finite number? Or do we know?

If there are an infinite number of numbers, wouldn't there be an infinite number of primes?

I was looking at the first several hundred primes and counting the number of primes in certain ranges (e.g. 0-99, 100-199 ... ) and I noticed that primes tended to become less and less frequent as the numbers increased. This may not hold true as the numbers get very large, but if it does, perhaps they continue to decrease in frequency until eventually you get to the last prime after which there are no primes.

There are an infinite number of primes. Here's the proof:

Suppose that there are only a finite number: {a0,a1,a2,...,an}. Now consider the number x = (a0*a1*a2*...an)+1. We know from the Fundamental Theorem of Arithmetic (http://mathworld.wolfram.com/FundamentalTheoremofArithmetic.html) that every number is either prime or uniquely factorable as the product of primes. But x isn't prime (since it isn't in our list), nor can we factor it into the product of primes since if you divide it by any of the primes in the list, you get a remainder of 1. Therefore, our original assumption that there are only a finite number of primes is wrong.

Yes, there are an infinite number of primes, but they do become more sparse as the numbers get larger.

Here's a harder one you might like to think about:

There are many <i>pairs</i> of primes, which differ by 2 - for example:

3, 5
11,13
41,43

It is currently an unanswered question as to whether there is an infinite number of such pairs, or only a finite number.

Answering this question one way or another would gain you the sort of fame associated with the solution to Fermat's last theorem.

Good luck. :)

So we have a new weekend riddle :)

Originally posted by kastner
every number is either prime or uniquely factorable as the product of primes.

mhhh... 8: it is not prime because its divisibility by 2 and 4... and it can be factorized as 2(4)... while 4 is not prime... what do you men with "uniquely factorable as the product of primes"?
========================================
think it: whole = sum(parts). we know that primes are a subconjunt of integers, the half by example... as integers are infinite we have # of primes = infinite / 2 = infinite ;)

Originally posted by fmonroy
mhhh... 8: it is not prime because its divisibility by 2 and 4... and it can be factorized as 2(4)... while 4 is not prime... what do you men with "uniquely factorable as the product of primes"?
8 is uniquely factorable as the product of prime numbers because 2*2*2 = 8, and 2 is a prime number.think it: whole = sum(parts). we know that primes are a subconjunt of integers, the half by example... as integers are infinite we have # of primes = infinite / 2 = infinite ;) You can generate an infinite number of integers from just a single prime number. Just take 2^x, where x is any integer, and you get an infinite number of integers.

Originally posted by Nasor
8 is uniquely factorable as the product of prime numbers because 2*2*2 = 8, and 2 is a prime number.

nice: kastner demostration is prfct!

Originally posted by Nasor
You can generate an infinite number of integers from just a single prime number. Just take 2^x, where x is any integer, and you get an infinite number of integers.

ok, but the question was: is the # of primes finite or infinite?

As james points out the number of primes is infinite. The big question is whether the number of prime pairs is infinite.

Another good question to ponder is <a href="http://mathworld.wolfram.com/GoldbachConjecture.html">Goldblachs' Conjecture</a>

With this whole take of multiplying 2*2*2 and so on. There are prime numbers that are closely related to numbers in that form. A Mersenne prime is a prime of the form 2^P-1. The first Mersenne primes are 3, 7, 31, 127. Not all numbers of this form are prime numbers. There are only 39 of these babies known. There is a "search" for more of these numbers. There's also a huge cash award for the discover(s) of a 10,000,000-digit prime. Super computers take quite some time to decide whether a number like that is a prime or not. For example, I run an AMD-1600XP and I use a program that calculates prime numbers, my computer has been testing 2^17440850 for nearly 2 months straight, and it's 60% done, that's insane computing time.

The following are all Mersenne prime numbers.
2^13466917-1
2^6972593-1
2^3021377-1
2^2976221-1
2^1398269-1

In closing: Because there is an infinite number of numbers, I theorize that there is also an infinite number of prime numbers. Just it's gonna be hell to find them.

*edit*- In response to the prime pair question. I find it highly unlikely for there to be an infinite number of prime pairs because the trend of prime numbers seems for them to become more spread out as they increase in size. But I'm not totally ruling out the possibility of it, because infinity is, well, infinity, and it's full of surprises.