-1
$\begingroup$

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)

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Eoin Dec 12 '14 at 7:28
0
$\begingroup$

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

$\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.