Euclid's proof on the infinity of primes

Question

Could someone shed some light on this? I perfectly understand Euclid's proof on the infinity of primes.

Let's suppose there is a largest prime, p, and then let's make a number, n, so that n = (2 x 3 x 5 x ... x p) + 1. ( The parentheses are not mandatory but they help me to visualize it better.) The new number n is a number larger than the largest prime and therefore it has to be a composite number. But if you divide n with any of the primes from 2 to p (that's all the primes), you always get a remainder of 1, so n can't be a composite number. So either there is a prime bigger than p that divides n, or n itself is a new prime number.

But I just don't understand the way my math book proves it. It begins exactly the same:

...The new number n is a number larger than the largest prime and therefore it has to be a composite number. Therefore it can be divided to it's prime factors. But because n is a sum with one of the addends being indivisible by any prime (the number 1), the number n must also be indivisible by any prime. Therefore n is a composite number that is divisible with some larger prime than p.

The part I don't really get is "But because n is a sum with one of the addends being indivisible by any prime, the number n must also be indivisible by any prime."

Answer 1

In essence, Euclid shows that for every prime number there is a greater one.

An integer of the form $p_{1}\cdots p_{k} + 1$ where $p_{1} \cdots p_{k}$ are primes is not divisible by any $p_{i}$, for if some $p_{i}$ divides it then $p_{i}$ divides 1, impossible.

Answer 2

I agree the the statement is confusing, and wrong, to my way of reading it; for a simple counter-example, 3+1 =4, which is, "a sum with one of the addends being indivisible by any prime (the number 1)", and yet the number 4 is clearly divisible by a prime (2).

I think your book may have tried for a clever way to describe it, and come out incorrect. Your description of the proof is as I understand it. I like the paren, which makes it more intuitive to me.

Answer 3

Don't put too much worth into the text. To quote it again:

But because $n$ is a sum with one of the addends being indivisible by any prime (the number 1), the number $n$ must also be indivisible by any prime.

It simply does not follow from $n=a+b$ and $p\nmid b$ that $p\nmid a$. In this point the author forgot to mention that $p\mid a$ is an essential part of the construction. I'd say, ignore the text book and be aware that you know the proof better. Also, that proof uses (without need) that composites can be completely factored into a product of primes. It would be sufficient to characterize composites as properly divisible by at least one prime.