Results 1 to 4 of 4

Thread: 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), $\displaystyle (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 $\displaystyle 3^k (mod 4)$...
    ?
    <<




    Calculate $\displaystyle n$ so that $\displaystyle \sum_{p \in \mathbb{P},p\leq n}\frac{1}{p}>5$
    Where $\displaystyle \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 $\displaystyle \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 $\displaystyle n\in \mathbb{Z}^+$ that satisfies $\displaystyle n\equiv 3 (\bmod. 4)$ must have at least one prime divisor $\displaystyle p\equiv 3 (\bmod. 4)$ - prove this! -, now try to construct a number which is $\displaystyle \equiv 3 (\bmod.4)$ but not multiple of any of the "finite" number of primes $\displaystyle \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: $\displaystyle \sum_{p\leq n} {\frac{1}{p}} \geq \log \log (n+1) - \log \zeta( 2) $

    Proof

    We have $\displaystyle 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 $\displaystyle e^x \geq 1+x$ )

    $\displaystyle \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 $\displaystyle \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 $\displaystyle \prod_{p}{\left(1 - \tfrac{1}{p^2}\right)} = \frac{1}{\zeta(2)}$ so with this and (1) we are done. $\displaystyle \square$

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

    Now, finding the smallest $\displaystyle 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 $\displaystyle \equiv 3 (\mod.4)$ I get a number that is $\displaystyle \equiv 3^k (\mod.4)$ so it is $\displaystyle \equiv 3 (\mod.4)$ or $\displaystyle \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 $\displaystyle \equiv 3 (\mod.4)$. Using your lemma * (which I can prove). This number has to have a prime divisor $\displaystyle \equiv 3 (\mod.4)$. Only thing I need to show now, is that this divisor is not one of the prime numbers $\displaystyle n_0,...n_k$. If it was, it would be a divide the difference of $\displaystyle n_0\cdot n_1\cdot ...n_k$ and $\displaystyle n_0\cdot n_1\cdot...n_k+4$which is 4 which leads to a contradiction, and the same goes for 6, because the smalles prime number that is $\displaystyle \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 $\displaystyle p_0,...,p_k$ then their product is congruent to $\displaystyle 3^{k+1}$

    As an alternative picking: $\displaystyle 4\cdot p_0 ... p_k -1$ also works.
    Last edited by PaulRS; Feb 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: Oct 22nd 2011, 12:37 PM
  2. Prime numbers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Dec 29th 2010, 04:54 AM
  3. prime numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 31st 2010, 09:44 AM
  4. Prime- numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 27th 2010, 11:04 PM
  5. Prime numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 20th 2009, 02:28 PM

Search Tags


/mathhelpforum @mathhelpforum