Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to prove 'infinite primes' kind of problem

  1. Jun 18, 2011 #1
    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. jcsd
  3. Jun 18, 2011 #2


    User Avatar
    Science Advisor

    The Euclidean proof is so neat and simple, I cannot imagine why you would want a different proof.
  4. Jun 18, 2011 #3

    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.
  5. Jun 18, 2011 #4
    There are many many proofs of the infinitude of the primes


    And about 1/4 of the way down through this

    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.
  6. Jun 19, 2011 #5
    One proof due to the German mathematician Kummer:

    Let P[itex]_{r}[/itex]:={2,3,5,7,...,p[itex]_{r}[/itex]} the finite set of all primes

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

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

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

    Therefore our assumption must be false
  7. Jun 19, 2011 #6


    User Avatar
    Science Advisor

    The above proof is essentially equivalent to euclids proof.
  8. Jun 20, 2011 #7
    I think not.

    Recall the original version of Euclids proof:

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

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

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

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

    Now compare this to the Kummer proof I cited.
  9. Jun 20, 2011 #8
    The following proff is due to Polya

    Let e:=2[itex]^{k}[/itex] and F[itex]_{k}[/itex]:=1+2[itex]^{e}[/itex] be the Fermat numbers

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

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

    From the recurrence relation we have the following

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

    Now let F:={F[itex]_{0}[/itex],F[itex]_{1}[/itex],F[itex]_{2}[/itex],...} 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[itex]_{r}[/itex]:={2,3,5,...,p[itex]_{r}[/itex]} can meet the requirements
    of our Lemma, there would simply be not enough primes.
  10. Jun 20, 2011 #9
    Let P:={p[itex]_{i}[/itex]} = {2,3,5,7,...} and
    E[itex]_{k}[/itex]:=1+[itex]\prod[/itex][itex]^{k}_{i=1}[/itex]p[itex]_{i}[/itex] be the Euclid numbers with E[itex]_{1}[/itex]:=3, E[itex]_{2}[/itex]:=7, E[itex]_{3}[/itex]:=31. etc

    We have the following

    Lemma All E[itex]_{i}[/itex] are odd, i.e. 2 is not a factor of E[itex]_{i}[/itex].

    and it is not difficult to prove the following

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

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

    This proof was inspired by the Polya proof
  11. Jun 20, 2011 #10
    From the Euler [itex]\zeta[/itex]-function [itex]\zeta[/itex](s):=[itex]\sum[/itex][itex]^{\infty}_{i=1}[/itex]([itex]\frac{1}{i}[/itex])[itex]^{s}[/itex]

    we know, that [itex]\zeta[/itex](2) is [itex]\frac{\pi^{2}}{6}[/itex]

    This quantity is irrational, since [itex]\pi[/itex] itself is irrational

    From the Euler product formula, we have

    [itex]\zeta[/itex](2):=[itex]\prod[/itex](1 - [itex]\frac{1}{p^{2}}[/itex])[itex]^{-1}[/itex], 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 [itex]\frac{\pi^{2}}{6}[/itex],
    which concludes the proof.
  12. Jun 20, 2011 #11


    User Avatar
    Science Advisor

    Yes, it is not equivalent, but "essentially" equivalent. It doesn't contain any new ideas.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook