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.

  • $\begingroup$ 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. $\endgroup$ – Hawk Jan 24 '14 at 21:33
  • $\begingroup$ Are you trying to prove that there are infinitely many primes? $\endgroup$ – Hawk Jan 24 '14 at 21:37
  • 1
    $\begingroup$ Nothing is wrong with this proof! $\endgroup$ – Woria Jan 24 '14 at 21:39
  • 1
    $\begingroup$ @woso why should $q|P$ imply $q|M$ and $q|N$? $\endgroup$ – Hawk Jan 24 '14 at 21:45
  • 1
    $\begingroup$ @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)$. $\endgroup$ – 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.

  • $\begingroup$ 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.] $\endgroup$ – coffeemath Jan 24 '14 at 22:58
  • $\begingroup$ @coffeemath you were right, I just fixed it! $\endgroup$ – Woria Jan 25 '14 at 0:21
  • 1
    $\begingroup$ 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) $\endgroup$ – coffeemath Jan 25 '14 at 0:27
  • $\begingroup$ 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.) $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – emka Jan 24 '14 at 22:06
  • $\begingroup$ @nhru Please update your answer to the intended proof, then I will update my answer to correspond to that. $\endgroup$ – Bill Dubuque Jan 24 '14 at 22:09
  • $\begingroup$ I believe I have made the appropriate update. $\endgroup$ – emka Jan 24 '14 at 22:21
  • $\begingroup$ I like the "Hint". (+1) $\endgroup$ – Woria Jan 25 '14 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.