# 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), $\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.

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

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