# Homework Help: Number Theory-limitation of Pn

1. Nov 10, 2009

### icystrike

1. The problem statement, all variables and given/known data

This is part of Euclid's proof such that he says:
1)

$$P_{n+1}$$ smaller or equal to $$P_{1}$$$$P_{2}$$...$$P_{n}$$ +1
Such that p_n is to denote some prime
I am wondering if anyone could provide me with an elegant prove to the above inequality as i am new to number theory.

2. Relevant equations

3. The attempt at a solution
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

Last edited: Nov 11, 2009
2. Nov 10, 2009

### HallsofIvy

That is part of Euclid's proof of what? The "$p_1p_2\cdot\cdot\cdot p_n+ 1$" reminds me of Euclides proof that there are an infinite number of primes but he never asserts that $p_{n+1}$ is smaller than or equal to that.

It does, of course, follow from Euclid's proof. Assuming that $p_1$, $p_2$, ..., $p_n$ is a list of all primes less than or equal to $p_n$, $p_1p_2\cdot\cdot\cdot p_n+ 1$ is certainly not divisible by any of $p_1$, $p_2$, ..., $p_n$. Therefore it is either a prime itself or is divisible by a prime larger than any of $p_1$, $p_2$, ..., $p_n$. In either case there must be a prime less than or equal to $p_1p_2\cdot\cdot\cdot p_n+ 1$

Last edited by a moderator: Nov 12, 2009
3. Nov 10, 2009

### SrEstroncio

It is not very elegant but the proof follows from the principles of order on the real number field.

Considering positive primes: given $$p_{1} < p_{2}$$, then it follows that $$p_{1} < p_{1}^2 < p_{1} \cdot p_{2}$$, by inductive reasoning you can prove that $$p_{n+1}<p_{n+1} \cdot p_{1} < p_{n+1} \cdot p_{1} \cdot p_{2}$$, and so on.

4. Nov 11, 2009

### Gib Z

Am I understanding the question right? It seems to come quite simply by noting that the primes are larger than 1. We can even omit the equality option of the inequality at a glance.

5. Nov 11, 2009

### icystrike

Thank you for all your replies (=

I think i'm able to understand the concept.

Let $$P_{1}$$$$P_{2}$$...$$P_{n}$$ +1 =N
Such that N is an element of positive integer.
Thus, it suggest N is co-prime to $$P_{1}$$,$$P_{2}$$, ... ,$$P_{n}$$

Which may be a prime number that is $$P_{k}$$
Such that k is a value larger or equal to n+1

OR

It may be a composite number that is larger than $$P_{n+1}$$ as the smallest possible divisor of N should be $$P_{n+1}$$ . Noting N is co-prime to $$P_{1}$$,$$P_{2}$$, ... ,$$P_{n}$$ .

Last edited: Nov 11, 2009