Algebra question involving prime numbers

[Darkiekurdo]

Homework Statement

Let the prime numbers, in order of magnitude, be p₁, p₂ ... Prove that p_n+1 ≤ p₁p₂...p_n + 1

Homework Equations

The Attempt at a Solution

I have no idea how to start. I think it involves reductio ad absurdum.

 

[Dick]

Look up Euclid's proof that there are an infinite number of primes. You can adapt it directly.

 

[Darkiekurdo]

Okay. So we want to 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 p₁, p₂, ..., p_n.

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

N = p₁p₂ ... p_n + 1.

N must have a prime factor. This prime factor must be one of p₁, p₂, ..., p_n, 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 p_n+1 ≤ p₁p₂ ... p_n + 1.

Let's assume it is false, so: p_n+1 ≥ p₁p₂ ... p_n + 1.

Now consider the number N ≥ p₁p₂ ... p_n + 1 where N = p_n+1.

This number must have a prime factor, so we will have to divide by a prime number which is one of p₁, p₂, ..., p_n.

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.

 

[Dick]

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.

 

[Darkiekurdo]

What is p_j, a prime number? And why does it follow that j>n?

 

[tiny-tim]

Now consider the number N ≥ p₁p₂ ... p_n + 1 where N = p_n+1.

This number must have a prime factor …

Hi Darkiekurdo!

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

You need to consider N - 1.

 

[Dick]

What is p_j, a prime number? And why does it follow that j>n?

Read what I wrote carefully. pj is a prime number that divides M. It's not one of p1...pn. So j>n.

 

[Darkiekurdo]

Ah I see it now. Thanks to the both of you!