A community for students.
Here's the question you clicked on:
 0 viewing
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_{n1}+1\) for all integers \(n\) with \(n\geq3\).
I need ideas on how to tackle this.
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_{n1}+1\) for all integers \(n\) with \(n\geq3\). I need ideas on how to tackle this.

This Question is Closed

JamesJ
 4 years ago
Best ResponseYou've already chosen the best response.1By 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 \]

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0the 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

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0I'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? :/

JamesJ
 4 years ago
Best ResponseYou've already chosen the best response.1There's nothing with sat73's argument. The induction argumentor at least the version of it I knowhinges 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_{k1} + 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.

JamesJ
 4 years ago
Best ResponseYou've already chosen the best response.1**Not P(k+1) implies [not implieD]

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0I see. :/ So, what Satellite is saying is that if \(p_1...p_{n1}+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_{n1}\).
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.