I Don't Understand This Proof of Infinitely many Primes

Question

The Proof

What Confuses Me

I follow the proof up until the point highlighted by the red square. I realize we must have $p_j|a$ (all composite numbers have a prime divisor) but why do we have the subsequent parts of the statement?

Answer 1

The proof is badly worded. Inside the box it should say $p_j|(a-p_1p_2...p_k)$ therefore $p_j|1$, which is not possible. Proof by contradiction is a method where you assume the converse of the proposition and then show that leads you to something impossible.

Answer 2

For any integers $x$, $y$, and $z$, if we have $x\mid y$ and $x\mid z$, then $x\mid (y-z)$.

(For example, when $x=2$, this says that the difference of any two even numbers is again even.)

In your situation, $x=p_j$, $y=a$, and $z=p_1p_2\cdots p_k$.

Answer 3

I think you didn't understand that line the intended way. Since we have both $p_j \mid a$ and $p_j \mid p_1 p_2 \cdots p_k$, we can conclude that $p_j$ divides the difference $a - p_1 p_2 \cdots p_k$, and the difference is in fact $1$.

Answer 4

For anyone wondering the same thing as I did, the proof works like this:

Suppose there are finitely many primes. The set of these finite primes is {$ p_1,p_2,p_3..p_k$}

Let $a = p_1*p_2*p_3*\cdots *p_k + 1$ that is a is the product of all the prime numbers plus 1

We know that $a$ is greater than any of the prime numbers on the list (remember that $a$ is all the prime numbers times themselves plus 1)

We know that a is a composite number(because it is bigger than all our prime numbers and therefore not a prime number and therefore a composite) so it must have a prime divisor

We will call this prime divisor $p_j$ so we can say $p_j|a$ since $p_j$ is also a prime it must be a divisor of the product of all prime numbers so we can say $p_j|p_1*p_2*p_3*\cdots*p_j*\cdots*p_k$

By the property of $x|y \wedge x|z \implies x|(y-z)$ we can say that $(p_j|a \wedge p_j|p_1*p_2*p_3*\cdots*p_k)\implies p_j|(a-p_1*p_2*p_3*\cdots*p_k)$ remember that $a = p_1*p_2*p_3*\cdots *p_k + 1$ so $(a-p_1*p_2*p_3*\cdots*p_k) =(p_1*p_2*p_3*\cdots *p_k + 1) - (p_1*p_2*p_3*\cdots *p_k) = 1$ so the idea that there are finitely many primes actually implies that $p_j|1$ which is impossible because that is saying $\frac{1}{p_j}$ is an integer which is only possible when $p_j = 1$ which is impossible because $p_j$ is prime and thus cannot be one. Therefore, by contradiction, there are not finitely many primes, which means there are infinitely many primes.