anonymous
  • anonymous
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.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
JamesJ
  • 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 \]
anonymous
  • 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
JamesJ
  • JamesJ
Actually, that's better

Looking for something else?

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

More answers

anonymous
  • 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? :/
JamesJ
  • 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.
JamesJ
  • JamesJ
**Not P(k+1) implies [not implieD]
anonymous
  • 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}\).

Looking for something else?

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