1
$\begingroup$

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."

$\endgroup$
2
  • $\begingroup$ "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." means $n=1+p_1 p_2 ... p_n$ then n is not divisible by any of the $p_i$ (since the remainder is 1 always.) Since it is composite, it has to be divisible by some prime other than $p_i$. Hence that prime must be greater than any of the $p_i$. $\endgroup$
    – Neeraj Kumar
    Commented Sep 12, 2015 at 12:21
  • $\begingroup$ Note that by construction $n = 2\cdot 3 \cdots p + 1$, where $2,3,\dots, p$ are ALL primes no greater than $p$. :) $\endgroup$
    – Yes
    Commented Sep 12, 2015 at 12:27

3 Answers 3

Reset to default
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ But how does "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." differ from, for example "Because 14 + 1 is a sum with one of the addends being indivisible by three, the number 14 + 1 must also be indivisible by three." which is just wrong? $\endgroup$
    – user265554
    Commented Sep 12, 2015 at 12:25
  • $\begingroup$ Note that by construction $n = 2\cdot 3 \cdots p + 1$, where $2,3, \cdots, p$ are ALL the primes no greater than $p$. :) The example $14+1$ is a pseudo one, because $3$ is not a prime factor of $14$. $\endgroup$
    – Yes
    Commented Sep 12, 2015 at 12:47
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is exactly what I was wondering! You can check my answer to Gudson Chou's comment. $\endgroup$
    – user265554
    Commented Sep 12, 2015 at 12:30
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .