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!
Best Answer
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.