Results 1 to 12 of 12

Math Help - Infinitely many primes

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    Infinitely many primes

    Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?
    A famous way is to show  \sum_{p \text{ prime}}\frac1p diverges.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by chiph588@ View Post
    A famous way is to show  \sum_{p \text{ prime}}\frac1p diverges.
    That harmonic series of course diverges since p=1 but I am confused on how showing divergence proves there are infinitely many primes.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    That harmonic series of course diverges since p=1 but I am confused on how showing divergence proves there are infinitely many primes.
    This isn't the harmonic series. We're only summing over the prime numbers. i.e.  \sum_{p \text{ prime}}\frac1p = \frac12+\frac13+\frac15+\frac17+\frac{1}{11}+\frac  {1}{13}+\cdots

    This proves infinitely many primes because if there were only finitely many primes, then  \sum_{p \text{ prime}}\frac1p couldn't possibly diverge.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by chiph588@ View Post
    This isn't the harmonic series. We're only summing over the prime numbers. i.e.  \sum_{p \text{ prime}}\frac1p = \frac12+\frac13+\frac15+\frac17+\frac{1}{11}+\frac  {1}{13}+\cdots

    This proves infinitely many primes because if there were only finitely many primes, then  \sum_{p \text{ prime}}\frac1p couldn't possibly diverge.
    Is there a specific test I would use then show divergence and hence conclude there are infinitely many primes?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    Is there a specific test I would use then show divergence and hence conclude there are infinitely many primes?
    Proof that the sum of the reciprocals of the primes diverges - Wikipedia, the free encyclopedia

    I don't really like this proof because the first step takes the log of infinity, but it will give you the right idea and can be tweaked a bit to be valid.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by chiph588@ View Post
    Proof that the sum of the reciprocals of the primes diverges - Wikipedia, the free encyclopedia

    I don't really like this proof because the first step takes the log of infinity, but it will give you the right idea and can be tweaked a bit to be valid.
    I don't really like any of those.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by dwsmith View Post
    I don't really like any of those.
    Maybe you'll like this one better: Goldbach's Proof of the Infinitude of Primes (1730)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by dwsmith View Post
    Is there a way to prove there is are infinitely many primes without doing a proof by contradiction?
    Euclid's proof can be modified into a constructive proof that there is no largest prime.

    CB
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Here's a proof I thought about a while back (which probably exists elsewhere!). It's not rigorous, as one doesn't really make precise the idea of putting "half" of the integers in a set. However, it's still an interesting reasoning.

    Suppose there are only n primes, the greatest being p.
    Half of the integers are not divisible by 2.
    Two-thirds of those are not divisible by 3.
    Four fifths of those are not divisible by 5.
    All the way to : (p-1)/pths are not divisible by p.

    Hence the "proportion" of integers not divisible by any one of 2, 3, \dots, p is equal to \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\dots \left(1-\frac{1}{p}\right), which is greater than 0, which is absurd because every integer must be a multiple of one of 2, 3, \dots, p, which we've supposed to be the only primes.

    The reasoning also shows informally that \prod_{p}\left(1-\frac{1}{p}\right)=0; expanding the product yields a nice Dirichlet series for the Möbius \mu function. Note also that the product is 1/\zeta(1).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    There is a famous relationship due to Euler: 1+\frac12+\frac13+\dots(continues forever) =(1+\frac12+\frac1{2^2}+\dots)\times(1+\frac13+\fr  ac1{3^2}+\dots)\times\dots\times(1+\frac1p+\frac1{  p^2}+\dots)\times\dots

    The left-hand side is the harmonic series that diverges. The right-hand side is a product in which each member is of finte value (for example: 1+1/2+1/2^2+\dots=2, 1+1/3+1/3^3+\dots=3/2. In general, 1+1/p+1/p^2+\dots=p/(p-1)).

    The right-hand side, then must be an infinte product because the harmonic series is divergent.
    Last edited by melese; July 3rd 2010 at 06:42 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by chiph588@ View Post
    Maybe you'll like this one better: Goldbach's Proof of the Infinitude of Primes (1730)
    This was beautiful ! Thanks

    I have a much less consequential question (related to the approach used in the Goldbach's proof)

    Let a,b be co-prime

    Let
    a1 = a
    a2 = a1 + b
    a3 = a1a2 + b
    a4 = a1a2a3 + b
    ....
    ...
    .

    Prove that (ai,aj) are also co-prime for any i and j

    Now I struggled with this one - finally could do it using induction. But I'm looking for a better way to do it? Can anyone help plz? I will be more than happy to submit my proof if anyone needs to see that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 8
    Last Post: May 29th 2010, 09:46 AM
  2. Infinitely many primes of the sequence 3n + 2
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 11th 2009, 02:32 AM
  3. infinitely many primes of the form 6k + 5 and 6K + 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2009, 05:25 AM
  4. Infinitely Many Primes
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 24th 2009, 06:12 PM
  5. infinitely many primes
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 18th 2008, 07:07 AM

Search Tags


/mathhelpforum @mathhelpforum