I was checking that if product of first n primes+1 gives a prime again is true to how many n
For example $$2+1=3$$ is a prime$$2\times 3+1=7$$ is a prime$$2\times 3\times 5+1=31$$ is a prime$$2\times 3\times 5\times 7+1=211 $$ is a prime$$2\times 3\times 5\times 7\times 11+1=2311$$ is a prime $$2\times 3\times 5\times 7\times 11\times 13+1=30031$$ is composite
So prime chain is broken and further steps will give composite no.s only
Now as I understood from proof of infinite primes Euclid said multiply all primes and add 1 and you will get another prime. It proves that there are infinite primes
Then my question is how can we guarantee that the resulting number is prime??
Or it should be that we will get another prime dividing the resulting number
Please help me to clear my confusion!!!!
$\endgroup$ 74 Answers
$\begingroup$From Wikipedia:
Consider any finite list of prime numbers $p_1, p_2,\cdots , p_n.$ It will be shown that at least one additional prime number not in this list exists. Let $P$ be the product of all the prime numbers in the list: $P = p_1p_2...p_n$. Let $q = P + 1$. Then let us check if $q$ is prime or not:
$(1)$: If $q$ is prime, then there is at least one more prime than is in the list.
$(2)$: If $q$ is not prime, then some prime factor $p$ divides $q$. If this factor $p$ were on our list, then it would divide $P$ (since $P$ is the product of every number on the list); but $p$ divides $P + 1 = q$. If $p$ divides $P$ and $q$, then $p$ would have to divide the difference of the two numbers, which is $(P + 1) − P = 1$. Since no prime number divides $1, p$ cannot be on the list. This means that at least one more prime number exists beyond those in the list.
This proves that for every finite list of prime numbers there is a prime number not on the list, and therefore there must be infinitely many prime numbers.
$\endgroup$ 2 $\begingroup$The proof relies on the fact that every prime is in that product, and that a prime can't divide both a number and that number plus one.
Assume there are finitely many primes. If $c$ is their product, then $p$ divides $c$ for any prime $p$. Therefore $p$ does not divide $c+1$ for any prime $p$. This is a contradiction, every integer has a prime divisor (for primes, this divisor is itself).
Note that $30031 = 59 \times 509$. Neither $59$ nor $509$ were included in your product and so there is no contradiction. The proof doesn't claim that this product of primes plus one construction always yields a prime.
$\endgroup$ 1 $\begingroup$Euclid's proof of infinite primes is not to give a method of generating infinite primes, it is to prove that there are cannot be a finite set of primes, which are two very different things.
It is non-constructive and the entire basis of the proof is to show that assuming a finite set of primes will lead to a contradiction by definition since $a \times b \times c \times d \ \times .... + 1$ cannot be divisible by any of the product terms if $a, b, c, ... \in \mathbb{N}$ as this would say that $\frac{1}{a}$ is an integer.
$\endgroup$ 2 $\begingroup$Neither Euler nor Euclid said any such thing. Euclid wrote that if $p_1,..,p_n$ are primes and $q$ is $1$ more than their product , then any prime divisor of $q$ is a prime not equal to any of $p_1,...,p_n.$
If $p$ is the least $m>1$ that divides $q$ then $p$ is a prime divisor of $k.$ So $q$ does indeed have a prime divisor.
$\endgroup$
