# How to prove 'infinite primes' kind of problem

1. Jun 18, 2011

### l-1j-cho

Other than the Eucledean method
(1+p1p2p3...)and so on

other than this, how do we prove that there are infinte prime numbers?
in algebreic way (excluding analyses)

Last edited: Jun 18, 2011
2. Jun 18, 2011

### HallsofIvy

The Euclidean proof is so neat and simple, I cannot imagine why you would want a different proof.

3. Jun 18, 2011

### l-1j-cho

indeed

but I was just wondering if there is any other technique to prove there are infinite primes so it can be applied to prove twin prime conjecture, mersenne prime conjecture, or sophie-germain conjecture.

4. Jun 18, 2011

### Bill Simpson

There are many many proofs of the infinitude of the primes

http://primes.utm.edu/notes/proofs/infinite/

And about 1/4 of the way down through this
http://en.wikipedia.org/wiki/Prime_number

and many more, but I hesitate to claim an infinite number of them.

However thus far nobody no one has seen how to use these to prove any of the conjectures you mention.

On a brighter and prime related note, there is now a non-crank proposed proof of Goldbach that has been submitted. It would be interesting to see if that could be explained in a form that those not in the "bright student" group could understand.

5. Jun 19, 2011

### RamaWolf

One proof due to the German mathematician Kummer:

Assumption:
Let P$_{r}$:={2,3,5,7,...,p$_{r}$} the finite set of all primes

form the prime factorial p$_{r}$#:=2*3*5*...*p$_{r}$
and the number q:=-1+ p$_{r}$#

q is not in P$_{r}$, that means, q is composite, with prime
factors from P$_{r}$; let p$_{k}$ be one of those factors

Now: p$_{k}$ divides both p$_{r}$# and q, hence it
must divide their difference: but this difference is 1
and p$_{k}$ does NOT divide 1.

Therefore our assumption must be false

6. Jun 19, 2011

### disregardthat

The above proof is essentially equivalent to euclids proof.

7. Jun 20, 2011

### RamaWolf

I think not.

Recall the original version of Euclids proof:

Let Q$_{r}$:={q$_{1}$, q$_{2}$,...,q$_{r}$} be the set a r distinct
prime numbers, and set q:=1+q$_{1}$*...*q$_{r}$

(Note: the r primes must NOT be the first r primes 2,3,..,p$_{r}$ !)

Then q is NOT divisible by any of the q$_{i}$ and must therefore be an new
prime or at least a composite number formed with additional primes.

Therefore: from any Q$_{r}$ you can construct a Q$_{r+1}$, and that proves the infinitude of the primes

Now compare this to the Kummer proof I cited.

8. Jun 20, 2011

### RamaWolf

The following proff is due to Polya

Let e:=2$^{k}$ and F$_{k}$:=1+2$^{e}$ be the Fermat numbers

with F$_{0}$:=3, F$_{1}$:=5, F$_{3}$:=17. F$_{4}$:=257, F$_{5}$:=65537, F$_{6}$:=4294967297, etc

we have the recurrence relation F$_{k+1}$:=2+$\prod$$^{k}_{i=0}$F$_{i}$

From the recurrence relation we have the following

Lemma: Any two F$_{i}$ and F$_{j}$ for distinct i, j are co-prime,
i.e. have no factors in common

Now let F:={F$_{0}$,F$_{1}$,F$_{2}$,...} be the set of all Fermat numbers and this set is countable,
i.e. has the cardinality of N:={1,2,3,4,...}, the set of the natural numbers

Therefore no finite P$_{r}$:={2,3,5,...,p$_{r}$} can meet the requirements
of our Lemma, there would simply be not enough primes.

9. Jun 20, 2011

### RamaWolf

Let P:={p$_{i}$} = {2,3,5,7,...} and
E$_{k}$:=1+$\prod$$^{k}_{i=1}$p$_{i}$ be the Euclid numbers with E$_{1}$:=3, E$_{2}$:=7, E$_{3}$:=31. etc

We have the following

Lemma All E$_{i}$ are odd, i.e. 2 is not a factor of E$_{i}$.

and it is not difficult to prove the following

Theorem Any two E$_{i}$, E$_{j}$ for different i,j are co-prime, i.e. have no common factors.

Now supose, P:={2,3,5,7,...,p$_{r}$}, then the corresponding {E$_{i}$} must be the numbers {2,3,5,7,...,p$_{r}$}
in some order (our Theorem), but that is impossible (our Lemma)

This proof was inspired by the Polya proof

10. Jun 20, 2011

### RamaWolf

From the Euler $\zeta$-function $\zeta$(s):=$\sum$$^{\infty}_{i=1}$($\frac{1}{i}$)$^{s}$

we know, that $\zeta$(2) is $\frac{\pi^{2}}{6}$

This quantity is irrational, since $\pi$ itself is irrational

From the Euler product formula, we have

$\zeta$(2):=$\prod$(1 - $\frac{1}{p^{2}}$)$^{-1}$, where the product is taken over all primes

If there were only a finite number of primes, this product would
be a rational number, in contradiction to the irrational nature of $\frac{\pi^{2}}{6}$,
which concludes the proof.

11. Jun 20, 2011

### disregardthat

Yes, it is not equivalent, but "essentially" equivalent. It doesn't contain any new ideas.