1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Algebra question involving prime numbers

  1. Apr 18, 2008 #1
    1. The problem statement, all variables and given/known data
    Let the prime numbers, in order of magnitude, be p1, p2 ... Prove that pn+1 ≤ p1p2...pn + 1

    2. Relevant equations

    3. The attempt at a solution
    I have no idea how to start. I think it involves reductio ad absurdum.
    Last edited: Apr 18, 2008
  2. jcsd
  3. Apr 18, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Look up Euclid's proof that there are an infinite number of primes. You can adapt it directly.
  4. Apr 18, 2008 #3
    Okay. So we wanna show that there are infinitely many prime numbers. Let's assume that there are only a finity amount of prime numbers which we'll label as p1, p2, ..., pn.

    Now let's consider some number, N, which is obtained by multiplying all prime numbers and adding 1:

    N = p1p2 ... pn + 1.

    N must have a prime factor. This prime factor must be one of p1, p2, ..., pn, because they are all the prime numbers. But this causes a contradiction since N leaves a remainder of 1 when divided by any of the prime numbers.

    Conclusion: there are infinitely many prime numbers.


    Now let's go to our problem: we want to show that pn+1 ≤ p1p2 ... pn + 1.

    Let's assume it is false, so: pn+1 ≥ p1p2 ... pn + 1.

    Now consider the number N ≥ p1p2 ... pn + 1 where N = pn+1.

    This number must have a prime factor, so we will have to divide by a prime number which is one of p1, p2, ..., pn.

    But we can't do this because this leaves a remainder of 1, which leads to a contradiction.

    Is it something like this? Sorry for the long post but this way I can summarise everything up for myself.
  5. Apr 18, 2008 #4


    User Avatar
    Science Advisor
    Homework Helper

    You're off to a good start. But the end is a little muddled. Call M=(p1p2...pn)+1. M has a prime factor, call it p, that is NOT one of the p1...pn. Good so far. Since p=pj for some j, it must be that j>n. Ok so far? Since you are listing the primes in ascending order it follows that p=pj>=pn+1. Since p is a factor of M, p<=M. So pn+1<=p<=M.
  6. Apr 18, 2008 #5
    What is pj, a prime number? And why does it follow that j>n?
  7. Apr 18, 2008 #6


    User Avatar
    Science Advisor
    Homework Helper

    Hi Darkiekurdo! :smile:

    No … N = pn+1 is prime, isn't it (it's the next prime after pn)? :redface:

    You need to consider N - 1. :smile:
  8. Apr 18, 2008 #7


    User Avatar
    Science Advisor
    Homework Helper

    Read what I wrote carefully. pj is a prime number that divides M. It's not one of p1...pn. So j>n.
  9. Apr 18, 2008 #8
    Ah I see it now. Thanks to the both of you!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook