Is Prime Finite?

1. Nov 17, 2004

JasonRox

So is it?

Something I have been thinking about lately.

2. Nov 17, 2004

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.

3. Nov 17, 2004

JasonRox

There is no formula for finding primes yet? Right?

4. Nov 17, 2004

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.

5. Nov 18, 2004

Tide

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

6. Nov 18, 2004

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.

7. Nov 18, 2004

matt grime

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

8. Nov 18, 2004

jcsd

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

9. Nov 18, 2004

James R

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

10. Nov 18, 2004

Atheist

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.

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?

Last edited: Nov 18, 2004
11. Nov 18, 2004

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.

12. Nov 18, 2004

jcsd

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

13. Nov 18, 2004

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.

14. Nov 18, 2004

shmoe

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.

15. Nov 18, 2004

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.

16. Nov 18, 2004

shmoe

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).

17. Nov 18, 2004

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.

18. Nov 19, 2004

Alkatran

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.

19. Nov 19, 2004

shmoe

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)

20. Nov 19, 2004

Alkatran

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...

21. Nov 19, 2004

Muzza

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

22. Nov 19, 2004

shmoe

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.

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.

23. Nov 19, 2004

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

Last edited: Nov 19, 2004
24. Nov 20, 2004