A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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_{n-1}+1\) for all integers \(n\) with \(n\geq3\). I need ideas on how to tackle this.

  • This Question is Closed
  1. JamesJ
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Actually, that's better

  4. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

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

  7. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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}\).

  8. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.