# Infinite primes - proof of new prime for composite

In proof of infinitude of primes, it is stated that $p_1p_2...p_n +1$ has no factor in the list of product (i.e., $p_1$ to $p_n$) due to addition with 1. However, the resulting value can be a prime or composite. If it is a prime, it is no issue as a new prime has been found. But, if a composite has been found then it has to be a product of at least 2 primes. I want proof that in the case of composite number, the prime factor is a new one and cannot be from the list.

My proof approach would state that it is obvious that none of the given primes would divide the composite number, and hence the prime factorization would have new primes. Stated differently, any prime in the list would not divide any part (factor) of the new number.

But, it is non-rigorous and if some help be provided to make it look rigorous, or else I should accept that it is an axiom and no rigor is possible.

• All you need is that $p_j\nmid(p_1\cdots p_n+1)$ for $1\le j\le n$. Is this not evident to you? – Lord Shark the Unknown Nov 19 '17 at 12:32
• It is obvious, but is there something that uses some sort of logic in formal form (say using connectives, etc.) that make it obvious in a rigorous way. In fact, I thought there must be some such proof for advanced courses. – jiten Nov 19 '17 at 12:35

You do not have to think of creating any new prime numbers. If you suppose that $p_1, \cdots, p_n$ are the only primes, and consider $q=p_1p_2\cdots p_n+1$ then first we note that $q\neq p_i$ for any $i$ so $q$ cannot be a prime number. So it has to be a composite number made up of primes $p_1, \cdots, p_n$ and therefore $p_i\mid q$ for some $i$ but then $p_i\mid (q-p_1p_2\cdots p_n)=1$ and we would have $p_i=1$ which is false. So $q\neq 1$ is neither prime nor composite, a contradiction to the Fundamental Theorem of arithmetic.

• I hope you meant that q has to be either a new prime number, or a composite number. Also, please vet my elaboration of your proof: --Your proof relies on any linear combination of product of prime and 1 being divisible by any prime in the list, as the prime part of the linear combination is also divisible by all primes. And, 1 being also a linear combination. So, exactly one $p_i$ should be 1, and 1 is not a prime. Hence, proved by contradiction. – jiten Nov 19 '17 at 12:55
• Should I take no comment as affirmation of my elaboration. If yes, then it should form a sort of 'better' way of proving the needed. – jiten Nov 19 '17 at 13:01
• No I am not saying that $q$ can be a new prime number. The only primes are $p_1, \cdots, p_n$. Since $q$ is none of them, so $q$ has no option other than to be a composite number. – PJK Nov 19 '17 at 13:02
• But, it can be a new prime or composite - either. It can be easily proved by taking few initial cases. Say, 2*3+1=7, or 2*3*5+1=31. – jiten Nov 19 '17 at 13:05
• I also request your vetting my elaboration of your proof. – jiten Nov 19 '17 at 13:05

Suppose $p_1 p_2 \dots p_n$ has a factor $m$. If $m$ is prime, of course, you're done. If $m$ is not prime, then there is some prime $p \mid m$, so in fact $p \mid p_1 \dots p_n$ and so we've fallen into the first case again.

It's not that there's any more work to do in this case; it's just that in the composite case, you refer to the previous case again.

You suppose that $p_1,...,p_n$ are the only primes, so because any number has a prime factorisation some $p_j$ divides $p_1...p_n+1$ ( which cannot be prime since by assumption there are no primes but $p_1,...,p_n$) and $p_j|p_1...p_j...p_n+1$ implies $p_j|1$ which contradicts the fact that $p_j$ is prime.