## anonymous 4 years ago Show that if $$p_k$$ is the $$k$$th prime, where $$k$$ is a positive integer, then $$p_n\leq p_1\cdot p_2\cdot ...\cdot p_{n-1}+1$$ for all integers $$n$$ with $$n\geq3$$. I need ideas on how to tackle this.

1. JamesJ

By induction. Let P(n) be the statement you have above. First observe that P(3) is true, as $p_3 = 5 \leq 7 = 2 \cdot 3 + 1 = p_1p_2 + 1$

2. anonymous

the number on the right throws a remainder of 1 when divide by the first n - 1 primes, and so if it is the next prime you are done, (because of $\leq$ and if it is not the next prime then it is composite and therefore divisible by some prime number, but not one of the n - 1 primes listed

3. JamesJ

Actually, that's better

4. anonymous

I'm a little confused: it seems I'm supposed to use induction starting at $$n=3$$. Doesn't this mean that I can't really use analytical methods to prove this? :/

5. JamesJ

There's nothing with sat73's argument. The induction argument--or at least the version of it I know--hinges on something else which is even deeper and harder. In the induction step: we want to show for k greater than or equal to 3 that P(k) => P(k+1) Suppose this is not the case: that P(k) and not P(k+1). Not P(k+1) implied $p_{k+1} > p_1 ... p_k + 1$ $= p_k ( p_1 ... p_{k-1} + 1/p_k)$ $\geq p_k(p_k -1) + 1/p_k \ \ \ \text{ by P(k) }$ $\geq p_k(p_k -1)$ Now, it seems very plausible that this is false; i.e., $$p_{k+1} > p_k(p_k -1)$$ is false for all $$k \geq 3$$ But proving that rigorously is much, much harder than the result we were first asked to prove. So instead, use sat73's proof.

6. JamesJ

**Not P(k+1) implies [not implieD]

7. anonymous

I see. :/ So, what Satellite is saying is that if $$p_1...p_{n-1}+1=N$$ is the next prime, $$p_n$$, then we are done because of the equality, and that if it is not, then it must be a composite number larger than $$p_n$$ because it is not divisible by any of the listed primes and, because of the fundamental theorem of arithmetic, we know that $$N$$ has a unique prime factorization, which clearly has a prime that we have not listed. If my train of thought is on track, then I do not understand what this has anything to do with the RHS having a remainder of $$1$$ after dividing it by $$p_1...p_{n-1}$$.