• Support PF! Buy your school textbooks, materials and every day products Here!

Algebra question involving prime numbers

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


2. Homework Equations



3. The Attempt at a Solution
I have no idea how to start. I think it involves reductio ad absurdum.
 
Last edited:

Answers and Replies

Dick
Science Advisor
Homework Helper
26,258
618
Look up Euclid's proof that there are an infinite number of primes. You can adapt it directly.
 
107
0
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
Science Advisor
Homework Helper
26,258
618
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.
 
107
0
What is pj, a prime number? And why does it follow that j>n?
 
tiny-tim
Science Advisor
Homework Helper
25,789
249
Now consider the number N ≥ p1p2 ... pn + 1 where N = pn+1.

This number must have a prime factor …
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:
 
Dick
Science Advisor
Homework Helper
26,258
618
What is pj, 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.
 
107
0
Ah I see it now. Thanks to the both of you!
 

Related Threads for: Algebra question involving prime numbers

Replies
5
Views
995
Replies
5
Views
2K
  • Last Post
Replies
2
Views
358
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
2K
Top