# Euclid's Proof

1. Feb 18, 2010

### mlsbbe

Hi, I am having trouble understanding this proof.

Statement

If pn is the nth prime number, then pn $$\leq$$ 22n-1

Proof:

Let us proceed by induction on n, the asserted inequality being clearly true when n=1. As the hypothesis of the induction, we assume n>1 and the result holds for all integers up to n.

Then

pn+1 $$\leq$$ p1p2...pn + 1

pn+1 $$\leq$$ 2.22...22n-1 + 1 = 21 + 2 + 22+ ...+ 2n-1

Recalling the indentity 1 + 2 +22+ ...+2n-1=2n-1

Hence

pn+1 $$\leq$$ 22n-1+1

But 1 $$\leq$$ 22n-1 for all n; whence

pn+1 $$\leq$$22n-1+22n-1
=2.22n-1
=22n
completing the induction step, and the argument.

What I don't understand is why the proof uses p1, p2, etc as powers of two. What is the nature of the pn? Are they prime or what? Why use powers?

2. Feb 18, 2010

### srijithju

In the proof , it is not that p1 , p2 , p3 have been replaced by powers of 2 . All that it is saying is that :

p1.p2.p3.p4.....pn < 2 . (2^2) . (2^4) .... ( 2 ^ (2^n - 1 ) ).

This is because it is assuming the theorem to be true for p1 , p2 .. upto pn .