# Let $N$ be the product of the first $m$ primes and $M$ be the product of the first $n-m$ primes.

Could someone tell me if this proof is correct?

Suppose there are finitely many primes: $p_1,p_2,\cdots,p_n$ primes. Let $m<n$. Then let $N=p_1p_2p_3\cdots p_m$ and $M=p_{m+1}\cdots p_{n-1}p_n$. Let $P=M+N$. First, $P$ cannot be prime or else we have a prime bigger than $p_n$. So $P$ is composite, hence there exists a $p_i$ such that $p_i \mid P$. But if $p_i\mid P$, then $p_i \mid M$ or $p_i \mid N$. So $p_i \not\mid P$. Hence the $P$ has a prime factor not on the list.

• This is an incorrect proof. When $q$ divides a number, it can produce remainders $0,1,\ldots,q-1$. So,if the sum of remainders is $q$ then the condition holds. – Hawk Jan 24 '14 at 21:33
• Are you trying to prove that there are infinitely many primes? – Hawk Jan 24 '14 at 21:37
• Nothing is wrong with this proof! – Woria Jan 24 '14 at 21:39
• @woso why should $q|P$ imply $q|M$ and $q|N$? – Hawk Jan 24 '14 at 21:45
• @Hawk you are right, I didn't notice that. But still we can extract a correct proof from it by observing that $\gcd(N+M,N)=\gcd(N+M,M)=\gcd(N,M)$. – Woria Jan 24 '14 at 22:30

How about this: Suppose there are finitely many primes say $p_1,p_2,\dots,p_n$. Let $N=p_1p_2\cdots p_m$, $M=p_{m+1}\cdots p_{n-1}p_n$ and $P=M+N$, where $m<n$. Since any prime number divides exactly one of $N$ and $M$, so no prime divides $P$, i.e. $P=1$, a contradiction.

• The setup (now) of $M,N$ isn't right for any prime to divide exactly one of them. [That was OK in original post, in this answer it seems definitions of $M,N$ changed slightly.] – coffeemath Jan 24 '14 at 22:58
• @coffeemath you were right, I just fixed it! – Woria Jan 25 '14 at 0:21
• The only thing I'd add now is the reminder that for a prime $p$, from $p|M+N$ and $p|M$ would follow $p|N$ (from basic divisibility facts). Then from your remark about no prime dividing both $M,N$ it would follow $M+N$ has no prime divisors as you say. (and +1) – coffeemath Jan 25 '14 at 0:27
• Yes! In fact we can say that for any common factor of $M+N$ and $N$, and that's why $$\gcd(N+M,N)=\gcd(N+M,M)=\gcd(N,M)$$. (And thanks for vote.) – Woria Jan 25 '14 at 0:36

{Edit: updated to address the edited question with revised proof]
There are still problems with the argument. First, it is not easy to infer missing details in your proof because you seem to be mixing together a proof by contradiction with a direct proof. In a proof by contradiction one assumes that there are only finitely many primes then deduces a contradiction. In a direct proof one shows that the number of primes is not finite by proving that, given any finite set S of primes, there exists a prime not in S. Due to this mixing of methods, it is not clear what you mean when you write "But if $\,p_i\mid P,\,$ then $p_i \mid M$ or $p_i \mid N.\,$ So $\,p_i \not\mid P$."

Recommendation: use a direct proof, not one by contradiction. Proofs by contradiction of this are notoriously difficult for those without much practice in such methods (e.g. sci.math had many hundreds of incorrect attempts - perhaps more so than any other topic discussed there).

Hint  Instead, try this: $\,M$ coprime to $N\Rightarrow M+N\,$ is coprime to $MN = p_1\cdots p_n.\,$ Therefore the prime factors of $\, M+N$ do not lie in $\{p_1,\ldots, p_m\}$

This is a slight generalization of Euclid's idea for generating new primes. Euclid employed $\,1 + p_1\cdots p_n\,$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too. Note that Euclid's method is the special case $k=0.\,$ Introspecting on the essence of Stieltjies idea leads to the following

Key Idea $\,$ Coprimes to $\,c\,$ arise by partitioning into $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ all prime factors of $\,c,\,$ i.e.

Theorem $\,\ \ \color{#c00}a+\color{#0a0}b\$ is coprime to $\ c\:$ if every prime factor of $\,c\,$ divides exactly one of $\,a\,$ or $\,b.$

Proof $\$ If not then $\,a+b\,$ and $\,c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid a\,$ or $\,p\mid b.\,$ Wlog, say $\,p\mid b.\,$ Then $\,p\mid (a+b)-b = a,\,$ so $\,p\,$ divides both $\,a,b,\,$ contra hypothesis.  QED

Remark $\$ This idea frequently proves useful, e.g. see this recent problem.

• I made a mistake when typing this out. I meant to say, suppose $p_i | P$. Then $p_i|(M+N)$. But since $M$ and $N$ have no common factors, $p_i \not\mid M+N$. Hence $M+N$ has a prime factor not on the list. – emka Jan 24 '14 at 22:06
• @nhru Please update your answer to the intended proof, then I will update my answer to correspond to that. – Bill Dubuque Jan 24 '14 at 22:09
• I believe I have made the appropriate update. – emka Jan 24 '14 at 22:21
• I like the "Hint". (+1) – Woria Jan 25 '14 at 7:14