Euclid's Proof: Infinity of Primes

[kenewbie]

Euclid's proof:

1) Assume there is a finite number of primes.
2) Let Pn be the largest prime.
3) Let X be the P1 * P2 ... * Pn + 1

At this point the statement is that "X cannot be divided by P1 through Pn", but why is that? This is not self-obvious to me. How can I know this?

k

 

[HallsofIvy]

Because dividing by any of those primes gives a remainder of 1, not 0:

$$\frac{P_1P_2...P_{i-1}P_iP_{i+1}...Pn+ 1}{Pi}= P_1P_2...P_{i-1}P_{i+1}...Pn+ \frac{1}{P_i}$$
The first term is an integer but the second is not.

 

[Hurkyl]

Minor aside: "the infinity of primes" is bad grammar. The noun form is wrong here -- you want the adjective "infinite", such as in "the infinite set of primes".

 

[Hurkyl]

How can I know this?

Try dividing.

 

[kenewbie]

$$\frac{P_1P_2...P_{i-1}P_iP_{i+1}...Pn+ 1}{Pi}= P_1P_2...P_{i-1}P_{i+1}...Pn+ \frac{1}{P_i}$$
The first term is an integer but the second is not.

That made perfect sense, thank you!

k