# Thread: Collection of Prime Numbers

1. ## 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.

2. 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.

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+4$which 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.
- 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.