Is Prime Finite?

[JasonRox]

So is it?

Something I have been thinking about lately.

[James R]

Your question doesn't seem to make sense.

Do you mean "Is there a finite number of prime numbers?"

If so, the answer is no. It is easy to prove that there are infinitely many primes.

[JasonRox]

There is no formula for finding primes yet? Right?

[James R]

There are ways of checking if a given number is prime or not. There is no known formula which generates the nth prime from the number n, if that's what you mean.

[Tide]

There is no formula for finding primes yet? Right?

Eratosthenes' Sieve is a process that will give you primes as large as you please. The only requirement is lots of time and patience! :-)

[Ethereal]

What about factorisation? Does any formula exist which can factorise any numbers into primes, as large as we please? The last time I heard, the answer was no.

[matt grime]

Yes there is a way of doing it, but it takes far too long to do.

[jcsd]

There are formulas that explicitly give the nth prime, none of them are that useful though.

[James R]

Oops. My mistake, jcsd. I think you're right.

[Atheist]

Your question doesn't seem to make sense.

Do you mean "Is there a finite number of prime numbers?"

If so, the answer is no. It is easy to prove that there are infinitely many primes.
It´s actually so simple that I can post it here:
(1) Assume a nonempty finite set P of primes.
(2) Let X be the product of all these primes.
(3) X+1 does not divide by any element in P so P cannot be the set of all primes (as any number except One divides by at least one prime).
As this is true for all nonempty finite sets P the number of primes must be infinite or zero (hint: It isn´t zero :tongue:)

EDIT: Thank´s to Shmoe and StatusX for helping me out with my flawed and less elegant 1st approach.


There are formulas that explicitly give the nth prime, none of them are that useful though.
Formulas in the sense of "prime(n) = ... " or algorithms to determine it (the latter is trivial)? What do you mean by saying they are not usefull? Can you give links or names?

[StatusX]

Technically, the third step should be "none of the primes in the list divide it, so your list could not have been complete." Your third step is not self-evident.

[jcsd]

Formulas in the sense of "prime(n) = ... " or algorithms to determine it (the latter is trivial)? What do you mean by saying they are not usefull? Can you give links or names?


Here's one:

f(n) = \lfloor \theta^{3^n}\rfloor

where \theta is Mill's constant.

Infact Mathworld has an entry on such formulas:

http://mathworld.wolfram.com/PrimeFormulas.html

[Atheist]

Bad example as it doesn´t give the n-th prime but the link is interesting, thanks.

@StatusX: I don´t really see a problem with my post although I have to admit that I took that out of my head and didn´t bother to look up a more elegant proof somewhere. I will consider rephrasing what I wrote.

[shmoe]

@StatusX: I don´t really see a problem with my post although I have to admit that I took that out of my head and didn´t bother to look up a more elegant proof somewhere. I will consider rephrasing what I wrote.

Your conclusion in step 3 is false. For example if our list of primes is 2,3,5,7,11, 13, then X+1=3031=59*509, in other words it has divisors other than 1 and X+1. The consequence of how X is made from our list of primes is that X+1 has a prime divisor that is not on our list, and hence we get another prime.

[Atheist]

>> in other words it has divisors other than 1 and X+1

Not if my list of primes I start with is complete which was the assumtpion I started from. However, I realize how and why my post was misleading and/or improperly written.

Thanks for showing where the problem lied, I´ve edited the thing in a way StatusX proposed.

[shmoe]

>> in other words it has divisors other than 1 and X+1

Not if my list of primes I start with is complete which was the assumtpion I started from. However, I realize how and why my post was misleading and/or improperly written.

No, if you start with assuming a complete list of primes you still can't conclude that X+1 has no divisors other than 1 or itself, only that none of your primes divide it (there is a distinction here). Add this to an earlier result that every integer has a prime divisor and you have a contradiction (this prime divisor may or may not be X+1).

[kreil]

(K+2){1-[WZ+H+J-Q]^2-[(GK+2G+K+1)(H+J)+H-Z]^2-[2N+P+Q+Z-E]^2

-[16(K+1)^3(K+2)(N+1)^2+1-F^2]^2
-[E^3(E+2)(A+1)^2+1-O^2]^2
-[(A^2-1)Y^2+1-X^2]^2
-[16R^2Y^4(A^2-1)+1-U^2]^2
-[((A+U^2(U^2-A))^2-1) x (N+4DY)^2+1-(X+CU)^2]^2
-[N+L+V-Y]^2
-[(A^2-1)L^2+1-M^2]^2
-[AI+K+1-L-I]^2
-[P+L(A-N-1)+B(2AN+2A-N^2-2N-2)-M]^2
-[Q+Y(A-P-1)+S(2AP+2A-P^2-2P-2)-X]^2
-[Z+PL(A-P)+T(2AP-P^2-1)-PM]^2}

Those are all minus signs on the left.

I guess the way it works is you plug 26 numbers in for each variable, A-Z, and after you plug in all the (infinitely many) combinations it spits out all of the primes. Some combinations don't work and produce negative numbers. Any positive number it produces will be a prime.

[Alkatran]

Your conclusion in step 3 is false. For example if our list of primes is 2,3,5,7,11, 13, then X+1=3031=59*509, in other words it has divisors other than 1 and X+1. The consequence of how X is made from our list of primes is that X+1 has a prime divisor that is not on our list, and hence we get another prime.

2*3*5*7*11*13 + 1 = 30 031

Proof:
All variables are whole numbers here
x*y mod x = 0
y*x mod x = 0
y=z*t
x*z*t mod x = 0
X times any number mod x is 0 thus X times the product of any numbers mod X is 0 thus X times the product of any numbers plus 1 mod x = 1 if X is greater than 1
x*z*t + 1 mod x = 1
x*z*t + 1 mod z = 1
x*z*t + 1 mod t = 1

You can say x is 2, z is 3, and t is 5 if you like.

[shmoe]

2*3*5*7*11*13 + 1 = 30 031


Yes, I typo'd a zero into oblivion, thanks for the correction.



Proof:
All variables are whole numbers here
x*y mod x = 0
y*x mod x = 0
y=z*t
x*z*t mod x = 0
X times any number mod x is 0 thus X times the product of any numbers mod X is 0 thus X times the product of any numbers plus 1 mod x = 1 if X is greater than 1
x*z*t + 1 mod x = 1
x*z*t + 1 mod z = 1
x*z*t + 1 mod t = 1

You can say x is 2, z is 3, and t is 5 if you like.

I don't see how this shows you get 30031 though. It will only show 2*3*5*7*11*13+1 is congruent to 1 mod 2, 3, 5, 7, 11, and 13. There are infinitely many numbers that satisfy this. (even better-there are infinitely many primes which satisfy this)

[Alkatran]

Yes, I typo'd a zero into oblivion, thanks for the correction.




I don't see how this shows you get 30031 though. It will only show 2*3*5*7*11*13+1 is congruent to 1 mod 2, 3, 5, 7, 11, and 13. There are infinitely many numbers that satisfy this. (even better-there are infinitely many primes which satisfy this)

The proof shows that
(2*3*5*7*11*13 + 1) mod (2, 3, 5, 7, 11, or 13) = 1
IE that it isn't divisible by any of them.

I'll need to think of how to show it's not divisible by any others...

[Muzza]

I'll need to think of how to show it's not divisible by any others...


Good luck, because as shmoe said, it's divisible by 59 and 509.

[shmoe]

The proof shows that
(2*3*5*7*11*13 + 1) mod (2, 3, 5, 7, 11, or 13) = 1
IE that it isn't divisible by any of them.


I see. From the format of your post it looked like you were trying to prove that 2*3*5*7*11*13+1=30,031. I wasn't disagreeing that X+1 wouldn't have any prime factors from the original list (I said as much) so it didn't cross my mind that you were trying to prove this.


I'll need to think of how to show it's not divisible by any others...

That was the point of my example, you can't show X+1 has only the trivial divisors since it's not in general true. The X+1 that you get is not necessarily prime. Though I botched a zero, the 59*509 factorization is still correct for that list of primes.

[Alkatran]

Well then think of it this way:

Since the number does not have any factors in the primes we counted (up to 13), we know that it has no factors which have factors in the known primes.

MEANING if it has a factor, that factor which is prime which is above our known primes! (if that factor is not prime, it means it has a factor which is prime or that factor has a fac..)

x*y*z + 1 mod (x,y or z) = 1 so x,y and z are not factors
thus if x*y*z + 1 has any factors, this factor will not have factors x,y or z
thus we must reach some factor which has no factors, or a prime

[Greg Bernhardt]

Think of a prime number as being a gap between the product of a number of primes (composite numbers). Because there is an infinitie number of composites, there will be an infinite number of gaps and thus an infinite number of primes.

[matt grime]

You're not a mathematician, right? Presuming there to be an infinite number of "gaps" since there are an infinite number of composites? Short of proving that there are an infinite number of gaps (ie primes) I don't see why anyone should accept that hypothesis.

[ZeAsYn51]

I think that Greg's just saying there is an infinite number of numbers. Saying that you'll run out of primes is like saying that you'll run out of multiples of two, or multiples of seven. You won't. Although the possiblity of coming across a prime gets smaller and smaller the higher up you go, there is still the possibility that a prime is there, you just have to look for it. I've developed a method of finding primes much like the sieve, but it only looks at two numbers at a time to determine if they're prime and uses the configuration of factors much like the sieve. My point is that no matter how many times I run through the numbers, there is always a "gap" somewhere down the line. The reason it becomes less likely to find a "gap" is because the larger the number the better a chance it has of having prime factors other then itself and one. So, I agree with Greg. I believe that primes are just as infinite as numbers themselves because just as multiples of two and multiples of seven are in the very structure of our number system, so are primes.

[shmoe]

Saying that you'll run out of primes is like saying that you'll run out of multiples of two, or multiples of seven.

I disagree with this. Running out of multiples of two means you would have only finitely many numbers. Running out of primes means no such thing. I wouldn't say these two assumptions have similar flavours at all.

I believe that primes are just as infinite as numbers themselves because just as multiples of two and multiples of seven are in the very structure of our number system, so are primes.

They are "just as infinite" in the sense of sets-there is a bijection between primes and naturals, but in a very real sense there are less primes than naturals, and less primes than there are mltiples of two. Primes 'thin out' as you get higher, multiples of two don't (this can be made very precise-e.g. the prime number theorem).

[ZeAsYn51]

Well, tell me exactly how any "set" (multiples of two,primes, etc.) of numbers is less than infinite if numbers themselves are infinite? That was my point.

[Gokul43201]

Well, tell me exactly how any "set" (multiples of two,primes, etc.) of numbers is less than infinite if numbers themselves are infinite? That was my point.

The set of all even primes.

[shmoe]

Well, tell me exactly how any "set" (multiples of two,primes, etc.) of numbers is less than infinite if numbers themselves are infinite? That was my point.

Let pi(x) be the number of primes less than or equal to x. The pi(x)~x/log(x), so pi(x)/x~1/log(x) and pi(x)/x->0 as x->infinity. Let two(x)=number of multiples of 2 less than or equal to x. Then two(x)/x->1/2 as x->infinity. In this sense there are less primes than multiples of two.

You'll notice I used the inherent order on the naturals here. Like I said, they are identitcal in size in the set theoretic sense.

[ZeAsYn51]

Okay, maybe I didn't use the best wording, but my point is that there is no proof that primes are finite in number and I do not believe there can be such a proof.

[shmoe]

Okay, maybe I didn't use the best wording, but my point is that there is no proof that primes are finite in number and I do not believe there can be such a proof.

Of course there can't be a proof that the primes are finite because they are not. See one of Atheist's post for a proof. (different proofs are available on request)

[ZeAsYn51]

Okay, Shmoe. I did go back and look at Atheists posts, but I didn't really find anything useful. I was, however, looking at what you just described to me (post #30) earlier today, but I'm not quite sure I understand it. Could you please take a few mins to explain it to me.

[Alkatran]

multiply all known primes together and add 1. This number cannot have any factors of the primes, or factors which have the primes as factors.

That means either the number is a higher prime or it has a factor which is of a higher prime.

[shmoe]

Okay, Shmoe. I did go back and look at Atheists posts, but I didn't really find anything useful. I was, however, looking at what you just described to me (post #30) earlier today, but I'm not quite sure I understand it. Could you please take a few mins to explain it to me.

Sure. pi(x)=number of primes less than or equal to x. So pi(3)=2, pi(3.5)=2, pi(10)=4, and so on. If you were to randomly select an integer less than x with uniform probability (equal chance of each) the probability you get a prime would be close to pi(x)/x. The prime number theorem tells us pi(x) is asymptotic to x/log(x) as x goes to infinity, so if x is very large the probability that a randomly selected integer between 1 and x is prime will be very close to 1/log(x). This goes to zero as x->infinity, so it's a fair thing to say that there are signifigantly less primes than there are natural numbers. The get sparse as you go higher, signifigantly sparse.

Compare with multiples of 2. If you randomly select an integer less than x the probability it will be a multiple of 2 is pretty close to 1/2, even for very large x. There is no sparseness with this sequence.

[Alkatran]

Sure. pi(x)=number of primes less than or equal to x. So pi(3)=2, pi(3.5)=2, pi(10)=4, and so on. If you were to randomly select an integer less than x with uniform probability (equal chance of each) the probability you get a prime would be close to pi(x)/x. The prime number theorem tells us pi(x) is asymptotic to x/log(x) as x goes to infinity, so if x is very large the probability that a randomly selected integer between 1 and x is prime will be very close to 1/log(x). This goes to zero as x->infinity, so it's a fair thing to say that there are signifigantly less primes than there are natural numbers. The get sparse as you go higher, signifigantly sparse.

Compare with multiples of 2. If you randomly select an integer less than x the probability it will be a multiple of 2 is pretty close to 1/2, even for very large x. There is no sparseness with this sequence.

You're asking it the number of primes is a 'countable' infinity or not?

For example, the area under y^x is countable as x goes from 0 to infinity if y < 1.

[matt grime]

This isn't about countability (or size), it's about distribution. Euclid's proof shows that the cardinality of the set of primes is the same as the set of naturals, but that is neither here nor there.

I don't think you know what countable means, judging by the last sentence, though.

[shmoe]

You're asking it the number of primes is a 'countable' infinity or not?

For example, the area under y^x is countable as x goes from 0 to infinity if y < 1.

I don't understand what you mean. The area under that graph will be finite, what do you mean by 'countable'?

[Alkatran]

This isn't about countability (or size), it's about distribution. Euclid's proof shows that the cardinality of the set of primes is the same as the set of naturals, but that is neither here nor there.

I don't think you know what countable means, judging by the last sentence, though.

No, I don't understand it. Explain, please?

I was thinking something along the lines of number or primes until x divided by x, does this number approach anything?

[matt grime]

Shmoe told you what happened - pi(x) is asymptotically x/logx (prime number theorem), see about 3 posts back.

A set is countable if it is in bijection with a subset of the natural numbers. (note I adopt the convention that finite sets are countable, some people restrict countable to mean infinite and in bijection with N, which I'd call countably infinite).

The area you obtain in your integral is finite, in the sense that is some real number, but it isn't really saying something about it as a set.

If we were to consider the set of points bound by the graph and the x axis then it is an uncountable set.

[mathwonk]

actually there is another step missing, and one that becomes important in trying to generalize euclid's result to other rings.

i.e. by definition a prime integer is a non zero integer which is not invertible, which boils down in the integers to not being equal to 1 or -1. So one must check the rather trivial fact that your number X+1 is not invertible,l i.e. that it is not equal to 1 or -1.


There are other interesting rings, such as a power series ring k[[X]] over a field, in which, whenever you add 1 to a product of series with no constant term, you do get an invertible element. in these rings, there are not an infinite number of essentially distinct primes. Indeed the only essential prime is X. Howvere since there is an infinite number of invertible elements u, all elements of form uX are prime, where u is invertible, but these are not essentially different from X.

If the field is finite, then there only a finite actual number of primes, even not taking equivalence into account.


when this question came up in graduate algebra, as to how to prove there are infinitely many prime integers, I naively asserted "Euclid proved that", (falsely assuming the rpoof would generalize to power series rings). My professor's retort was "Yes, but Euclid was intelligent!"

However, here is the actual proof of Euclid, and he does not actually fill in the step my professor implied he did. I was hustled! (But I have never forgotten the point I was hustled into noticing.)

"Prime numbers are more than any assigned multitude of prime numbers. Let A, B, and C be the assigned prime numbers.

I say that there are more prime numbers than A, B, and C.
Take the least number DE measured by A, B, and C. Add the unit DF to DE.

Then EF is either prime or not.

First, let it be prime. Then the prime numbers A, B, C, and EF have been found which are more than A, B, and C.
java applet or image Next, let EF not be prime. Therefore it is measured by some prime number. Let it be measured by the prime number G. VII.31 I say that G is not the same with any of the numbers A, B, and C.

If possible, let it be so.

Now A, B, and C measure DE, therefore G also measures DE. But it also measures EF. Therefore G, being a number, measures the remainder, the unit DF, which is absurd.

Therefore G is not the same with any one of the numbers A, B, and C. And by hypothesis it is prime. Therefore the prime numbers A, B, C, and G have been found which are more than the assigned multitude of A, B, and C.
Therefore, prime numbers are more than any assigned multitude of prime numbers."

(for the translation, google on euclid's elements.)