At another website someone made the claim that it is impossible to prove there are an infinite number of prime numbers. I recently took up the challenge and came up with the following proof:
1. Let N represent any integer between 1 and infinity.
2. Let X = 10^N.
3. Let A be the set of all whole numbers that divide into X without leaving any remainder. Set A will contain 2 and 5. Thus X is not a prime number.
4. Let P = X + 1. P may be a prime number because no number in set A can divide P without leaving a remainder of 1. Thus, P can only be divided by itself and 1.
5. So it appears that since N can be any integer between 1 and infinity, and since P is derived from N, there are an infinite number of prime numbers.
Caveat: Set A does not account for all the whole numbers outside of A which may or may not divide evenly into P. Since there are an unlimited number of such whole numbers, it may be impossible to test them all.
Of course Euclid came up with a proof that still stands today. Here is an excerpt from http://www.curiouser.co.uk/facts/pnproof.htm:
"Euclid proved that there are an infinite number numbers. He did this by first considering the possibility that there are a finite number of primes.
"He knew that by definition all non-prime numbers were expressible by multiply together different combinations of prime numbers. Then he considered multiply together all the known prime numbers and adding 1. He realised that this number could not be divisible by any of the known primes because dividing by any of the known prime numbers would leave a remainder of 1. This number would therefore either have to be prime itself, or be divisible by another prime number that was not known.
"In this way he was able to show that however many prime numbers were known, it would always be possible to show that there are more."
recommend
Facebook
Twitter
bookmark 
print
Comments: 17
X = 200
X + 1 = 201
But 201 / 3 = 67
X = 100
X + 1 = 101
So I'm afraid that it's oops for Dave. :-)
Anyway, the current proposal is to let X = 10^N and P = X+1.
But
N=3: 10^3+1 = 1001 = 7*11*13
N=4: 10^4+1 = 10001 = 73*137
N=5: 10^5+1 = 100001 = 11 * 9091
Euclid's version works because it multiplies together all known primes and then adds 1, making it certain that the new number is not divisible by any of the knows primes. It is, therefore, either a prime itself, or it's divisible by a prime yet unknown. Either way, it generates a new prime, which can then be plugged into the same process to generate yet another, ad infinitum.
You did of course explain that in your post, Gary, but I feel that thinking it over helps shed light on why your formula doesn't work. It is because your set A cannot pull the same trick as Euclid's set of "all known primes". When you add 1 to your X, it's true that the new number will not be divisible by numbers in set A (factors of X). It may, however, be divisible by other numbers. It is therefore not true that it must be a prime; or that, failing that, any number that can divide it must be an as-yet-unknown prime.
The number you get may be a prime, of course, but that doesn't prove that there's an infinite number of primes. In order to do that, you need something that must give us primes. (That would be true even if there were many more N's that your formula worked for than seems to be the case based on Dave's comment above.)