Hello I have been stuck on this for over an hour. I honestly don't even know where to start. Any help would be appreciated.
Let $\{p_1, p_2,…,p_r\}$ be a set of prime numbers, and let
$N = p_1\cdot p_2\cdot\ldots\cdot p_r+1.$
Prove that $N$ is divisible by some prime not in the original set. Use this fact to deduce that there must be infinitely many prime numbers.
Best Answer
Your subject line says it's about proving that $(p_1\cdots p_n)+1$ is divisible by some prime. Only in the body of the question do you say "not in the original set", i.e. the set whose members are $p_1,\ldots,p_n$.
It seems to me that proving it's divisible by some prime is the easier part. Every number in the sequence $2,3,4,5,6,\ldots$ is divisible by some prime. (Euclid did not consider $1$ to be a number, so he didn't need to say "except $1$". For him, $2$ was the smallest number.) You'll find Euclid stating and proving that every number is divisible by some primes. Supposing that is not the case, then there would be a smallest number $M$ not divisible by any prime. But if $M$ is not divisible by any prime smaller than $M$, then $M$ is prime itslef, and is divisible by itself.
Hence $(p_1 \cdots p_n)+1$ is divisible by some prime, either itself or some smaller prime.
The point is that none of the prime factors of $(p_1\cdots p_n)+1$ can be one of the primes $p_1,\ldots,p_n$. That is because when you divide $(p_1\cdots p_n)+1$ by any one of the primes $p_1,\ldots,p_n$, the remainder will always be $1$. For example, if you divide $(p_1\cdots p_n)+1$ by $p_1$, the quotient will be $p_2\cdots p_n$ and the remainder will be $1$. More concretely, suppose the primes in the original set are $2,5,11$. Then $(p_1\cdots p_n)+1$ is $(2\times5\times11)+1 = 111 = 3\times 37$.
If you divide $(2\times5\times11)+1 = 111$ by $2$, the quotient is $5\times 11$ and the remainder is $1$.
If you divide $(2\times5\times11)+1 = 111$ by $5$, the quotient is $2\times 11$ and the remainder is $1$.
If you divide $(2\times5\times11)+1 = 111$ by $11$, the quotient is $2\times 5$ and the remainder is $1$.
You have $2\times5\times11=110$.
The next number after $110$ that is divisible by $2$ is $110+2$.
The next number after $110$ that is divisible by $5$ is $110+5$.
The next number after $110$ that is divisible by $11$ is $110+11$.
Therefore $110+1$ cannot be divisible by $2$, $5$, or $11$.
So whichever primes divide $110+1$ must be primes other than $2$, $5$, and $11$.
That means we can extend the set $\{2,5,11\}$ to a larger set of primes. In this concrete example, the larger set is $\{2,3,5,11,37\}$.