2
$\begingroup$

I was wondering if I could get some insight on my proof. I am in the midst of relearning some number theory and just "writing proofs" in general, and I would like some assistance to see if I am on the right track.

The statement I am proving is Euclid's Theorem which states that "there are infinitely many primes."

Here is my attempt at the proof after some reading (keep in mind, I am still somewhat of an amateur when using LaTeX so please bear with me!):

Proof. Suppose in order to derive a contradiction there are finitely many primes. That is, we have a complete list $p_1, \dots, p_n$. Let $p$ be the product of all the primes in this list i.e. $p = p_1 \cdots p_n$. Consider the number $$N = p + 1.$$ Since $N > p_i$ for all $i$, $1 \leq i \leq n$, there is no way $N$ can be any of the $p_i$. So $N$ must be composite. By the Fundamental Theorem of Arithmetic, $N$ is a product of primes. So there is a prime, say q, that divides $N$, and $p$ as well. So it follows this $q$ must also divide $$N - p = 1,$$ but this is impossible. No number, or prime, divides 1. Thus, contradicts the assumption that our list is complete and so there must be infinitely many primes.

QED

Any feedback would be appreciated. I always had trouble understanding this theorem and always forgot the "key argument". Now I feel like I finally get it... Hopefully. Thank you for reading!

$\endgroup$
7
  • $\begingroup$ $N$ need not be composite. $2\times 3+1=7$, for example. Nor do you need the FTA, which is a lot harder to prove than this. All you need to know is that every natural number greater than $1$ is divisible by some prime. $\endgroup$ – lulu Apr 28 '16 at 1:39
  • $\begingroup$ On rereading, I see that you deduce the compositeness of $N$ by remarking that, were it prime, we'd already have the desired counterexample. Agreed. But, still, invoking the Fundamental Theorem of Arithmetic is not necessary. $\endgroup$ – lulu Apr 28 '16 at 1:43
  • $\begingroup$ I see how it is unnecessary now. Thanks for reading! $\endgroup$ – o_o Apr 28 '16 at 1:47
  • $\begingroup$ It is good. Petty comment, you say no number divides $1$. Well, $1$ divides $1$. However, it is certainly true that no number $\gt 1$ divides $1$, so no prime divides $1$. $\endgroup$ – André Nicolas Apr 28 '16 at 1:55
  • $\begingroup$ Oops, that was silly (LOL). Good catch. $\endgroup$ – o_o Apr 28 '16 at 1:57
5
$\begingroup$

I would not add the complication of making this into a proof by contradiction. Euclid did not do it that way, despite many modern authors, dating back at least to Dirichlet in the middle of the 19th century, asserting that Euclid did it that way.

Start with any finite set $S$ of prime numbers. (For example, we could have $S=\{2, 31, 97\}$) Let $p = 1 + \prod S$, i.e. $1$ plus the product of the members of $S$.

Then $p$ cannot be divisible by any of the primes in $S$. Therefore either

  • $p$ is itself prime, in which case there are more primes than those in $S$, or

  • $p$ is divisible by some other primes not in $S$, in which case there are more primes than those is $S$.

Thus every finite set $S$ of primes can be extended to a larger finite set of primes.

(For example, if $S=\{5,7\}$, then $1+\prod S = 1 + 35 = 36 = 2\times2\times3\times 3$, and the additional primes not in $S$ are $2$ and $3$.)

The initial assumption that $S$ contains all primes is at best a needless complication that serves no purpose.

$\endgroup$
6
  • 1
    $\begingroup$ I am always very confused about the whole debate between contradiction proof versus non contradiction. Yes, this proof never states "assume there are finitely many primes," but it also never actually proves that there are infinitely many primes, merely that any finite set of primes can be expanded. From there, the proof goes "there are infinitely many primes because the number of primes cannot be equal to some finite number $N$ (via the construction)" To me, however, this final statement is essentially a contradiction statement (assume finite, that's impossible, so we get a contradiction. $\endgroup$ – ASKASK Apr 28 '16 at 1:59
  • $\begingroup$ So to me, this proof is still a proof by contradiction, it's just that the actual contradiction part is postponed until after the construction $\endgroup$ – ASKASK Apr 28 '16 at 2:00
  • $\begingroup$ @ASKASK : If you want to look at it that way, it is still better not to create an illusion that the assumption of finiteness of the set of ALL primes somehow plays a role in the construction. $\endgroup$ – Michael Hardy Apr 28 '16 at 2:01
  • $\begingroup$ but doesn't the finiteness play a role? Finite number => finite set => construction of a prime not in that set. $\endgroup$ – ASKASK Apr 28 '16 at 2:03
  • $\begingroup$ @ASKASK : Finiteness of the arbitrary finite set of primes plays a role. An assumption of finiteness of the set of ALL primes plays no role in the construction, even if it plays a different role of the kind you suggest. $\endgroup$ – Michael Hardy Apr 28 '16 at 2:04
1
$\begingroup$

Your proof looks good. It is not exactly how Euclid's proved it, but it works, and most importantly you understand it.

A couple of minor points:

Like lulu said in the comments, invoking the Fundamental Theorem of Arithmetic isn't necessary. Also in the end you state "No number, or prime, divides 1." This technically isn't true since 1 divides 1. It would be enough just to say "No prime divides 1."

$\endgroup$
4
  • 1
    $\begingroup$ Yes, I understand the minor points. My personal understanding was the goal, haha. Thank you for reading! :) $\endgroup$ – o_o Apr 28 '16 at 2:04
  • $\begingroup$ In the context of Euclid, $1$ is not a number, so "No number divides $1$" would be correct. $\endgroup$ – Michael Hardy Apr 28 '16 at 2:05
  • $\begingroup$ @MichaelHardy Can you elaborate? Does Euclid not consider 1 a number? $\endgroup$ – M47145 Apr 28 '16 at 2:09
  • 1
    $\begingroup$ @M47145 : That has been my understanding. See this page: aleph0.clarku.edu/~djoyce/elements/bookVII/bookVII.html $\qquad$ $\endgroup$ – Michael Hardy Apr 28 '16 at 5:37

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.