0
$\begingroup$

I'm reading the book Discrete Mathematics and It's Applications written by Rosen. At page 260, there is a proof using the technique similar to Euclid's. The following is my trying to understand the proof.


Assume that there are only finitely many primes, $p_1, p_2, ..., p_n$, I'll call it prime list later on. Let

$$Q = p_1p_2\cdots p_n+1.$$

By the fundamental theorem of arithmetic, $Q$ is prime or else it can be written as the product of two or more primes.

Let $p_j$ be an arbitrary prime in the prime list. Then $p_j$ can't divide $Q$, since:

  1. If $p_j \mid Q$, then $p_j \mid (Q - p_1p_2\cdots p_n=1)$:

    The is because $p_j \mid (p_1p_2\cdots p_n)$, so $p_j \mid (1\cdot Q+(-1)\cdot(p_1p_2\cdots p_n))$.

  2. Since $p_j \mid (Q - p_1p_2\cdots p_n=1)$ is false, $p_j \not\mid Q$:

    The only integer which divides all integer is $1$, but $p_j$ is a prime.

Since $p_j \not\mid Q$ also means that $Q$ is not $p_j$, $Q$ is not in the prime list. And since there is no prime in the prime list divides $Q$, $Q$ can't be written as the product of two or more primes. Finally, $Q$ has to be a prime, which is not in the prime list. We've arrived a contradiction.


I'm not sure whether it's correct, but that's how I understand the proof. And the following is the proof in my book:

enter image description here enter image description here

I don't understand why it arrives the conclusion "Hence, there is a prime not in the list".

Please give me some hints...

$\endgroup$
  • $\begingroup$ Either $Q$ is prime or not. If it is prime, it is not in the "primes list" because it is greater than every prime in the list. Thus, $Q$ is not prime and hence must have a prime factor: but all primes are in the list (by assumption) and thus some of them must divide $Q$. $\endgroup$ – Mauro ALLEGRANZA Mar 16 '18 at 15:26
  • $\begingroup$ To @MauroALLEGRANZA: But how did you know it's greater than every prime in the list? $\endgroup$ – Ning Wang Mar 16 '18 at 15:35
  • $\begingroup$ Because is the product of them all plus 1 ! $\endgroup$ – Mauro ALLEGRANZA Mar 16 '18 at 15:40
  • 1
    $\begingroup$ Ugh. This book proof is everything I hate about logic introductions. 1) The Fundamental Theorem of Arithmetic is overkill. 2) This isn't a proof by contradiction but a proof of the negation: "the set of primes is not finite". 3) We could view this as a proof by contradiction of "you aren't unable to extend any finite list of primes", but it actually constructively proves the direct statement, perhaps worded "the set of all primes is more numerous than any assigned multitude of primes", so a proof by contradiction is silly. 4) As you probably guessed, the quoted statement is from Elements. $\endgroup$ – Derek Elkins Mar 16 '18 at 20:49
  • 1
    $\begingroup$ As far as I can tell, your issues with the given proof have to do with number-theoretic concerns which is consistent with the focus of all the answers. My comment does not address those issues which is why I didn't make it an answer. The motivation for my comment is annoyance (directed at the book) with the (very probable) confusion about "proof by contradiction" it is sowing and the subtle misrepresentation of classical (as in old) theorems and proofs. $\endgroup$ – Derek Elkins Mar 17 '18 at 2:13
1
$\begingroup$

The statement "$Q$ is prime or else it can be written as a product of two or more primes" implies there exists a prime dividing $Q$. Since none of the $p_j$ have this property, there has to be another prime not in the list which divides $Q$.

$\endgroup$
1
$\begingroup$

Let $p_j$ be a prime dividing $Q=p_1p_2\ldots p_n+1$. If $p_j$ is a prime in the list $p_1,p_2,\ldots,p_n$, then $p_j\mid Q-1$.

This means that there is some integer $k$ such that $Q=p_jk$ and some other integer $m$ such that $Q-1=p_jm$. Subtracting these two gives: $$1=Q-(Q-1)=p_j(k-m)$$ So $p_j$ divides $1$, but $p_j>1$, which is impossible

$\endgroup$
1
$\begingroup$

If $p$ is a prime number such that $p\mid Q$ then, since $Q-p_1p_2\ldots p_n=1$, $p\notin\{p_1,p_2,\ldots,p_n\}$ because otherwise $p\mid1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.