prime numbers. show that $p_{n+1} \le {p_1 \cdot \ldots \cdot p_n +1}$

80 Views Asked by At

Let $p_n$ be the n-th prime number.

show that $p_{n+1} \le {p_1 \cdot \ldots \cdot p_n +1}$

I´ve used a few primes and obtained the same result, even when this assumption seems trivial I have no idea how to prove this for the n-th prime.

I'd appreciate some help

1

There are 1 best solutions below

2
On BEST ANSWER

By the fundamental theorem of arithmetic we know that the number $r = p_1 \cdot \ldots \cdot p_n +1$ also has a prime decomposition. None of the primes $p_1,\dots,p_n$ can be a divisor of $r$ though, as $r = 1 \text{ mod }p$. Therefore some other prime $p_s$, $s \geq n+1$, needs to be a divisor of $r$, such that we get that $p_{n+1} \leq p_s$ and $p_s \leq r$ since $p_s$ is a divisor of $r$. Thus we have $p_{n+1} \leq r$

In case that you don't know the fundamental theorem of arithmetic, try to prove it with the following hint:

You can get the existence via induction and the uniqueness by using Euclid's Lemma (if a prime divides a product then also one of the two factors).