Results 1 to 4 of 4

Math Help - Collection of Prime Numbers

  1. #1
    CSM
    CSM is offline
    Junior Member
    Joined
    Oct 2010
    Posts
    56

    Lightbulb Collection of Prime Numbers

    This is bugging me for quite some time now, any hints are appreciated:

    Prove: Given any finite sequence of prime numbers which are equivalent to 3 (mod 4), (p_0,p_1,...,p_k) you can construct a new prime number which is equivalent to 3 (mod 4).

    Attempt: I immediately thought about Euclid's proof of the infinity of the collection of primenumbers. So maybe we should multiply the given primenumbers, which gives us a number that is equivalent to 3^k (mod 4)...
    ?
    <<




    Calculate n so that \sum_{p \in \mathbb{P},p\leq n}\frac{1}{p}>5
    Where \mathbb{P} represents the prime numbers.

    And of course I want the first n for which this is true. If any more theory is needed for the second question I can put it here, but it is vaguely written so I don't really get it. It is a constructive proof by Euler that shows that \sum_{n\in \mathbb{P}\frac{1}{n} is divergent.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    1. Note that any number n\in \mathbb{Z}^+ that satisfies n\equiv 3 (\bmod. 4) must have at least one prime divisor p\equiv 3 (\bmod. 4) - prove this! -, now try to construct a number which is \equiv 3 (\bmod.4) but not multiple of any of the "finite" number of primes \equiv 3 (\bmod.4) - adapt Euclid's proof so that you build a number congruent to 3 module 4.

    2. That series diverges but grows painfully slowly (there's a quote I heard that goes something like: " log log x tends to infinity, but no one has actually observed this in practice" )

    A lower bound would be: \sum_{p\leq n} {\frac{1}{p}} \geq \log \log (n+1)  - \log \zeta( 2)

    Proof

    We have e^{\sum_{p\leq n} {\frac{1}{p}} } = \prod_{p\leq n}{e^{\frac{1}{p}}} \geq \prod_{p\leq n} { \left(1 + \frac{1}{p}\right)} (since e^x \geq 1+x )

    \prod_{p\leq n} { \left(1 + \frac{1}{p}\right)} = \prod_{p\leq n}{\frac{\left(1 - \tfrac{1}{p^2}\right)}{\left(1 - \tfrac{1}{p}\right)}} \geq \prod_{p}{\left(1 -  \tfrac{1}{p^2}\right)} \cdot \prod_{p\leq n}{\left(\displaystyle\frac{1}{1-\tfrac{1}{p}}\right)} (1)

    Now from Euler's proof you should know that \prod_{p\leq n}{\left(\displaystyle\frac{1}{1-\tfrac{1}{p}}\right)} \geq 1 + \tfrac{1}{2} + ... + \tfrac{1}{n}\geq \log(n+1) and \prod_{p}{\left(1 -  \tfrac{1}{p^2}\right)} = \frac{1}{\zeta(2)} so with this and (1) we are done. \square

    So now using this we get that roughly for n \geq \exp(244,13) your inequality should hold. - observe how HUGE that is!

    Now, finding the smallest n for which the inequality holds is totally unreasonable in my opinion.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    CSM
    CSM is offline
    Junior Member
    Joined
    Oct 2010
    Posts
    56
    Thank you very much for your reply.
    I think I've got it now:
    If i multiply the primenumbers that are \equiv 3 (\mod.4) I get a number that is \equiv 3^k (\mod.4) so it is \equiv 3 (\mod.4) or \equiv 1 (\mod.4) in the first case we add 4 in the second case we add 6. In both cases we'll get a number that is \equiv 3 (\mod.4). Using your lemma * (which I can prove). This number has to have a prime divisor \equiv 3 (\mod.4). Only thing I need to show now, is that this divisor is not one of the prime numbers n_0,...n_k. If it was, it would be a divide the difference of n_0\cdot n_1\cdot ...n_k and n_0\cdot n_1\cdot...n_k+4which is 4 which leads to a contradiction, and the same goes for 6, because the smalles prime number that is \equiv 3 (\mod.4) is 7.

    As for the second question, I need to thank you again. I'll have to take a second look at it.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Well done, your idea will work!

    - a couple of details though: it is better to add 2 rather than 6 because 3 (which divides 6) is congruent to 3 module 4. also if you consider p_0,...,p_k then their product is congruent to 3^{k+1}

    As an alternative picking: 4\cdot p_0 ... p_k -1 also works.
    Last edited by PaulRS; February 19th 2011 at 07:09 AM. Reason: 4 p-0..p_k + 3 should have been 4 p_0...p_k - 1
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Prime numbers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: December 29th 2010, 04:54 AM
  3. prime numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 31st 2010, 09:44 AM
  4. Prime- numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 27th 2010, 11:04 PM
  5. Prime numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 20th 2009, 02:28 PM

Search Tags


/mathhelpforum @mathhelpforum