# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8636145,"math_prob":0.99937147,"size":2179,"snap":"2019-26-2019-30","text_gpt3_token_len":663,"char_repetition_ratio":0.11126437,"word_repetition_ratio":0.0,"special_character_ratio":0.31757686,"punctuation_ratio":0.19871795,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999728,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-16T04:06:59Z\",\"WARC-Record-ID\":\"<urn:uuid:adb1e45f-086c-4105-b453-1732b03161b7>\",\"Content-Length\":\"162058\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:930bf8c9-a221-4a97-b884-419c0f7ba1aa>\",\"WARC-Concurrent-To\":\"<urn:uuid:3632df0c-ee58-4447-a3d2-a22497393ccf>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/650342/let-n-be-the-product-of-the-first-m-primes-and-m-be-the-product-of-the-fir\",\"WARC-Payload-Digest\":\"sha1:HR3KMS37NMPHG4IAEO4OAWGYQ46E3NVO\",\"WARC-Block-Digest\":\"sha1:ZZXCDMM5XN7GLNF3XVVPSHQWKK6JGXVJ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195524502.23_warc_CC-MAIN-20190716035206-20190716061206-00452.warc.gz\"}"}