# Algebra question involving prime numbers

## Homework Statement

Let the prime numbers, in order of magnitude, be p1, p2 ... Prove that pn+1 ≤ p1p2...pn + 1

## The Attempt at a Solution

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

Last edited:

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

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.

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

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

tiny-tim
Homework Helper
Now consider the number N ≥ p1p2 ... pn + 1 where N = pn+1.

This number must have a prime factor …

Hi Darkiekurdo! No … N = pn+1 is prime, isn't it (it's the next prime after pn)? You need to consider N - 1. Dick