Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - my last question-infinite number of primes

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    123

    Exclamation my last question-infinite number of primes

    Please see the " Microsoft word" attachement. Thank you very much.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    The sum,
    \sum_p \frac{1}{p}
    Diverges.

    I will quote Wikipedia while doing this.
    This is the only proof I am familar with (I know there are many).
    ----
    You need to be familar with the Zeta function,
    \zeta (s)=\sum_{k=1}^{\infty} \frac{1}{n^s}
    It diverges for s\leq 1 (integral p-series test).
    Converges for s>1.
    ----
    You also need to be familar with one of the most elegant formulas, "Euler-Product formula".

    It states we can factorize the zeta function as,
    \zeta (s)=\prod_p (1-p^{-s})^{-1}
    ----
    The final concept you need to know is how to work with infinite products. If you an infinite product of positive terms,
    \prod a_k
    You can take the natural logarithm to obtain,
    \ln \prod a_k=\ln (a_1a_2...)=\ln a_1+\ln a_2+...= \sum \ln a_k
    And then work with convergence with the infinite series!
    ----
    Now we can begin with Euler's proof.
    ----
    \ln \sum_{n=1} \frac{1}{n}=\ln \prod_p (1-p^{-1})^{-1}
    By Euler's product formula.
    Expressing the product as a sum we have, (natural logarithms are positive)
    \sum_p \ln (1-p^{-1})^{-1}
    Exponent rule for logarithms,
    \sum_p -\ln (1-p^{-1})
    Infinite series for logarithm ( |p^{-1}|<1)
    Thus,
    \sum_p \frac{1}{p}+\frac{1}{2p^2}+\frac{1}{3p^3}+...
    But this is (absolute convergenct thus we can rearrange),
    \sum_p \frac{1}{p} +\sum_p \frac{1}{p^2}\left( \frac{1}{2}+\frac{1}{3p}+... \right)
    This is strictly less than,
    \sum_p \frac{1}{p}+\sum_p \frac{1}{p^2} \left(1+\frac{1}{p}+\frac{1}{p^2}+... \right)
    Geomteric series ( |1/p|<1),
    \sum_p \frac{1}{p}+\sum_p \frac{1}{p(p-1)}
    Now, if
    \sum_p \frac{1}{p}
    Converges.
    Then, by the dominance rule,
    0\leq \sum_p \frac{1}{p(p-1)}\leq \sum_p \frac{1}{p}
    Converges.
    That means,
    \ln \sum_{n=1}^{\infty} \frac{1}{n}
    Is bounded by this sum.
    Which is not possible because this is the infamous harmonic series which diverges.
    Q.E.D.
    ---
    Note, since the harmonic series behaves like \ln n and the sum of reciprical of primes is the natural logarithm of that we can say,
    \sum_p \frac{1}{p} \sim \ln \ln n
    (Note not a prove, an observation).
    Thus, it diverges really really slowly.
    ---
    Thus the number of primes is infinite.
    Because otherwise the reciprocal sum would converge.
    Last edited by ThePerfectHacker; December 27th 2006 at 12:23 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2006
    Posts
    123
    Hi perfecthacker,

    Thank you very much.

    As I understand from your post, the information you gave me is belonging to the later part of this question.

    Could you please show me how to do the beginning part?

    a) Prove that there are exactly 2j square-free numbers whose
    only prime divisors are in the set { p1, p2, ..., pj }.

    b) Prove that, for sufficiently large x,
    Nj(x)<= 2j * sqrt(x) (Hint: show every number can be written uniquely as the product of a perfect square and a square-free number).

    (c) Prove that,
    for sufficiently large x, Nj(x) < x. Why does this
    mean there must be an infinite number of primes?

    (d) For subsequent results, we need a little bit more. Prove that,
    for sufficiently large x, Nj(x) < x2 (The proof is
    exactly like the one in (c).)

    Thank you very much.

    This question seems difficult to me. If I misunderstand your post, please do let me know. Many thanks again.
    Last edited by CaptainBlack; December 28th 2006 at 06:27 AM. Reason: clarrify some of the non-printing charaters
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jenny20 View Post
    Hi perfecthacker,

    Thank you very much.

    As I understand from your post, the information you gave me is belonging to the later part of this question.

    Could you please show me how to do the beginning part?

    a) Prove that there are exactly 2^j square-free numbers whose
    only prime divisors are in the set { p1, p2, ..., pj }.
    .
    The square free numbers whose only prime divisors are in { p1, p2, ..., pj }
    are the numbers {p1^a1*p^2^a2*..*pj^aj, a1, .. aj in {0,1}}

    This is eqivalent to the set of all j-bit binary numbers. The number of j-bit binary numbers is 2^j.

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2006
    Posts
    123
    Many thanks Captainblack !
    Could you please teach me how to solve part b , part c, and part d too? Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2006
    Posts
    123
    I have forgotten to mention about this point :

    The attachment in the " Microsoft word" is a proof that there are an infinite number of primes.


    =================
    Please do guide me through this question. I am completely blank for b to d. Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jenny20 View Post
    b) Prove that, for sufficiently large x,
    Nj(x)<= 2j * sqrt(x) (Hint: show every number can be written uniquely as the product of a perfect square and a square-free number).
    First lets do what the hint suggests (though it is pretty obvious)

    Consider some positive integer x, and its prime decomposition:

    x=p_1 ^{a_1}p_2^{a_2}...p_m^{a_m},

    then:

    let  b_k = 2\,\lfloor a_k / 2 \rfloor , and c_k=a_k-b_k, then c_k=0 or c_k=1 \mbox{ for }k=1,..,m, and b_k is even.

    Then:

    x=B\,C

    where B=p_1 ^{b_1}p_2^{b_2}...p_m^{b_m} is a square, and C=p_1 ^{c_1}p_2^{c_2}...p_m^{c_m} is square free.

    Which proves the result in the suggestion.

    Now the number of squares less than or equal x\le \sqrt{x}, and by part (a) the number number of square free numbers with prime factors from amoung \{p_1,p_2, .. , p_j\} =2^j so:

    N_j(x)\le 2^j \sqrt(x)

    RonL

    Notes:

    \lfloor x \rfloor denotes the floor function for x, that is the greatest integer less than x.
    Last edited by CaptainBlack; December 28th 2006 at 07:00 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jenny20 View Post
    (c) Prove that,
    for sufficiently large x, Nj(x) < x. Why does this
    mean there must be an infinite number of primes?

    We have proven that:

    N_j(x) \le 2^j \sqrt(x),

    now if x>(2^j)^2, we have:

    N_j(x)<\sqrt{x}\,\sqrt{x}=x,

    as required.

    RonL
    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 Jenny20 View Post
    (d) For subsequent results, we need a little bit more. Prove that,
    for sufficiently large x, Nj(x) < x2 (The proof is
    exactly like the one in (c).)
    I don't understand (d) it is weaker than (c) unless the x2 is suppose to denote x/2, when the simple expedient of asking that:

    x>4 (2^j)^2

    gives the required inequality for large enough x.

    RonL
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Nov 2006
    Posts
    123
    Hi Captainblack,

    Thank you very much for your rely. Your answers very logical. I need your help for go on the next three part. Please! Please!

    Anyhow to show that the sum of the reciprocals of the primes diverges, it's
    enough to show that, for any j:
    1/pj+1 + 1/pj+2 + 1/pj+3 + .... > 1/2


    (e) Why is it enough to show that the above sum is greater
    than 1/2 ?

    (f) Show that for any x, x/pj+1 + x/pj+2 + x/pj+3 + .... >= x - Nj(x).
    (Hint: Explain first why x/p is greater than or equal to the number
    of numbers less than or equal to x that are divisible by p. What about
    x/p + x/q where p and q are relatively prime?)

    (g) Use the results from (d) and (f) to complete the proof
    that the sums of the reciprocals of the primes diverge.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    (e) If for any j:

    S_j=1/p_{j+1} + 1/p_{j+2} + 1/p_{j+3} + .... > 1/2

    then we can choose an m_1 such that:

     S_{j,m_1} = 1/p_{j+1} +.. 1/p_{m_1} > 1/4,

    and then:

    S_{m_1}=1/p_{m_1+1} + 1/p_{m_1+2} + 1/p_{m_1+3} + .... > 1/2

    then we can choose an m_2 such that:

     S_{m_1,m_2} = 1/p_{m_1+1} +.. 1/p_{m_2} > 1/4,

    and so on, so repeating this process k times we have:

    S_j=k/4+1/p_{n+1} + 1/p_{n+2} + 1/p_{n+3} + ... = k/4 + S_n >(k+2)/4

    for any k, so we find that S_j is greater than any number we care to name and so is divergent

    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Nov 2006
    Posts
    123
    Thank you very much Captainblack,

    Is your previous answer also cover part f and part g?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jenny20 View Post
    Thank you very much Captainblack,

    Is your previous answer also cover part f and part g?
    Not yet, I will be having a go at them shortly

    RonL
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Jenny20 View Post
    (f) Show that for any x, x/pj+1 + x/pj+2 + x/pj+3 + .... >= x - Nj(x).
    (Hint: Explain first why x/p is greater than or equal to the number
    of numbers less than or equal to x that are divisible by p. What about
    x/p + x/q where p and q are relatively prime?)
    I'm afraid this is not as clear as I would like it but here goes:

    First the hint:

    The numbers less than or equal to x divisible by p are:

    p, 2p, ... \lfloor x/p \rfloor p .

    There are \lfloor x/p \rfloor of these, which is \le x/p, which is the result required by first part of the hint.


    Now the number of numbers \le x divisible by p and or q is less than the sum of the number \le x divisible by p and the number divisible by q.

    So now:

    x/p_{j+1} + x/p_{j+2} + ....

    is greater than or equal to the number less than x which have prime divisors are among {p_{j+1}, p_{j+2}, ...}. This final number is equal to x-N_j(x) (as there are x numbers less than or equal to x and N_j(x) of these have primes divisors among p_1, .. p_j and no others, so:

    x/p_{j+1} + x/p_{j+2} + ...\ge x-N_j(x),

    as required.

    RonL
    Last edited by CaptainBlack; December 28th 2006 at 10:01 AM.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    from (f) we have:

    x/p_{j+1} + x/p_{j+2} + ...\ge x-N_j(x),

    from (d) we have:

    N_j(x)<x/2

    so:

    x/p_{j+1} + x/p_{j+2} + ...\ge x-N_j(x) > x-x/2=x/2

    Divide this through by x gives:


    1/p_{j+1} + 1/p_{j+2} + ...>1/2

    and (e) tells us that this means that:

    1/2 + 1/3 + .. + 1/p_n + ...

    diverges.


    RonL
    Last edited by CaptainBlack; December 28th 2006 at 10:19 AM.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Infinite Number Question
    Posted in the Algebra Forum
    Replies: 9
    Last Post: September 5th 2010, 05:03 PM
  2. infinite primes
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: January 30th 2009, 09:42 AM
  3. infinite primes?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2007, 04:42 PM
  4. Primes in an Infinite Sequence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 12:25 AM
  5. Infinite Primes Proof
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: April 11th 2005, 08:40 AM

Search Tags


/mathhelpforum @mathhelpforum