Prove that $p_1\cdot p_2 \cdots p_r +1$ is divisible by some prime 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.
 A: Compute $N\pmod {p_i}$ for each $i=1,\ldots,r$: $N\pmod {p_i}=1$ by definition of $N$, so therefore $N$ is not divisible by $p_i$. Then since every integer can be factored uniquely as a product of primes, it must be that $N$ is divisible by some prime, but we have just shown that it can't be divisible by $p_i$ for any $i=1,\ldots,r$.
Suppose that there are finitely many primes, $p_1,\ldots,p_r$. Then $N=p_1\cdot p_2\cdots p_r +1$ is a perfectly good number that must be divisible by some prime not in our set of primes $\{p_1,\ldots,p_r\}$, so we have a contradiction. Therefore, there are infinitely many primes.
A: Suppose, for the sake of contradiction,  that $N$ is divisible by at least one of them, say $p_i.$ Then $N=p_i\cdot q,$ for some integer $q.$ Then you have $$p_1\cdots p_{i-1}p_ip_{i+1}\cdots p_r+1=p_iq\Longrightarrow p_i(p_1\cdots p_{i-1}p_{i+1}\cdots p_r-q)=1$$ which implies that $p_i$ divides $1$ and hence $p_i\leqslant1.$ Since $p_i$ is positive, then $p_i\geqslant1$ and it follows that $p_i=1,$ which is absurd since $1$ is not a prime number. Hence, none of $p_1,p_2,\ldots,p_r$ divides $N$ and thus, any prime divisor of $N$ is not in $\{p_1,p_2,\ldots,p_r\}.$ Therefore, given any list $\{p_1,p_2,\ldots,p_r\}$ of primes, you will always be able to find a prime $p$ not in that list and it follows that there are infinitely many primes.
A: 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\}$.
A: $N=p_1p_2\dotsm p_r+1$ cannot be divisible by one of the $p_i$s, since it would imply such a $p_i$ would divide $N-p_1p_2\dotsm p_r=1$, while a prime number  is $\ge 2$.
Now, as $N>1$, it has divisors $>1$ ($N$ itself is one of them), so there is a smallest integer $n>1$ which divides $N$ (possibly $n=N$). This smallest non-trivial divisor is necessarily a prime number, otherwise it could be written as $n=ab$, with $a,b>1$, which would imply $n$ is not the smallest  divisor $>1$ of $N$.
This proves any finite list of primes is incomplete, hence the set of primes is infinite.
A: If $N = (p_1)\times(p_2)\times\cdots\times(p_n) + 1$ implies $p_1,p_2,p_3,...,p_n$ doesn't divide $N$. Now since every number is either prime or composite:
Case I: If $N$ is prime, then for a finite collection of prime, I can invent a new prime number namely $N$ and I repeat this process indefinitely by adding this new prime to that finite set. Hence the list becomes infinite. 
Case II: If $N$ is not prime implies $N$ is composite, hence should be divisible by a prime $t$ such that $t<N$. Since none of the $p_i$'s divide $N$ (why?) (also all $p_i$'s are less than $N$), implies there's an additional prime $t$ in the finite list. I add that $t$ to the finite prime set. Now again I construct a new $N'$ from the updated set of finite prime. You could show that is process too is never ending.
Hence the set of prime has infinite element implies there are infinitly many primes.
NOTE: This may not be exactly a formal proof, I only tried to illustrate the idea. Feel free to point out any error in my argument.
A: Quite simply, N leaves a remainder of 1 when divided by any prime in the set and is thus not divisible by any such. Then, N is either divisible only by itself and 1 (hence divisible by a prime not on the list) or it is a composite number with prime factorization consisting only of primes not on the list.
