# Help explain the end of this proof for infinitely many primes?

by contradiction, assume finitely many primes $p_1, p_2,\cdots, p_k$. let $N = p_1p_2\cdots p_k + 1$. Note $N > 1$. Now, by the fundamental theorem of arithmetic, there exists a number $p_j$, where $j$ is an element of $(1,2,...,k)$ such that $N = P_j\times q$. So, $p_1p_2\cdots p_k + 1 = p_j*q$. So, $1 = p_j*(q - p_1p_2p_3\cdots p_k)$. So $p_j|1$, but now we reached a contradiction, $p_j < 1$ but $p_j > 1$.

Can you please explain two parts

1) How does it become $1 = p_j(q-p_1p_2p_3\cdots p_k)$

2) the contradiction, why does it mean $p_j <1$, couldn't $p_j = 1$(but I guess it's still not a prime though)

First of all, you do not need to invoke the fundamental theorem of arithmetic (existence and uniqueness of prime factorization). You only need that any natural number $>1$ has some proper divisor (by the very definition of prime as "$>1$ and only divisible by $1$ and itself"), hence among these is a minimal proper divisor, and that must be prime (as any proper divisor would be a smaller proper divisor of the original number).

Now to your questions. From $$p_1p_2\cdots p_k+1=p_jq$$ by subtracting the long product $$1=p_jq-p_1p_2\cdots p_k$$ and then by observing that $p_j$ occurs among the factors of the long product $$1=p_jq-p_j(\cdot p_1\cdots p_{j-1}p_{j+1}\cdots p_k)=p_j\cdot (q-p_1\cdots p_{j-1}p_{j+1}\cdots p_k)$$

There's no need to conclude $p_j<1$. Indeed, it suffices to know that $1=ab$ with integers $a,b$ implies $a=b=\pm1$ (and not prime). Or simply that $p_j\nmid 1$ for all primes.

Since $p_j$ is a prime, it must be somewhere in our finite set. Then we subtract to get $1=p_jq-p_1p_2\cdots p_k=p_j(q-p_1p_2\cdots p_k)$ by the left distributive property. This shows that $p_j$ is a prime which divides $1$. Since $p_j|1$ it follows $p_j\leq 1$. But (we know $1$ is not a prime! this is by definition) we assumed $p_j>1$ a prime.

• As Hagen von Eitzen has said: it suffices to show that for integers $a,b\in \mathbb{Z}$, $1=ab$ if and only if $a,b = \pm 1$. However, this proof that you provide is not incorrect. I find it to be a simpler introduction from a learning perspective. But, the observations made by @Hagen von Eitzen are very much cleaner and in some sense "assume" less. – Eoin Dec 12 '14 at 7:28

(1) From rearranging the previous statement.

(2) Yes from $p_j \mid 1$ you get $p_j \le 1$, which as you say contradicts $p_j$ being prime.