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