How to prove that there are infinitely many primes without using contradiction

Question

How can I prove that there are infinitely many primes without using contradiction?

I know the proof that is (not) by Euclid saying there are infinitely many primes. It assumes that there is a finite set of primes and then obtains one that is not in that set.

Say for some reason I want to prove it without using contradiction. Maybe I'm contradictaphobic. How could I go about doing this?

Answer 1

Actually, that proof can be phrased in a way to avoid contradiction. Let ${\cal P}=\{p_1,...,p_n\}$ be a non empty finite set of primes. Then let $a=1+\prod_{p\in\cal P}p$.

By the usual argument there must be a prime $p\mid a$, $p\notin\cal P$. This proves that any finite set of primes cannot include all primes and so there must be infinitely many.

EDIT: Given the almost-infinite sequence of comments, let me spell out the "usual argument":

• $\emptyset\neq\cal P$ is a finite set of primes;
• $a=1+\prod_{p\in\cal P}p$;
• then $a\equiv1\bmod p$ for all $p\in\cal P$ and $a\neq\pm1$;
• but: for all $a\in\Bbb Z\setminus\{\pm1\}$ there exists a prime $q$ such that $a\equiv0\bmod q$
• $1\not\equiv0\bmod q$
• therefore $q\notin\cal P$;
• therefore there's no finite set containing all primes.

QED

Answer 2

The simplest direct proof I know is one which involves infinite series. One can show that $\sum\limits_{p\text{ prime}}\frac{1}{p}$ diverges. Particularly, it means that there cannot be finitely many primes since the sum of finitely many nonzero numbers is finite. (There is a very slight contradiction - or contrapositive - argument in here if you look closely enough.) That said, you should definitely combat your contradictaphobia... proofs by contradiction are everywhere in mathematics. Hamstringing yourself by not accepting or feeling at ease with such proofs will make mathematics quite challenging at times.

Answer 3

In the proof that is attributed to Euclid, what you are really doing is this: For any integer $n \geq 1$ you are producing a number, namely one plus the product of all primes less than or equal to $n$, whose prime factors have to be greater than the biggest prime less than $n$.

Therefore, given the fundamental theorem of arithmetic, Euclid's proof can be modified in such a way that it actually proves that for any integer $n \geq 1$ there exists a prime $p \geq n$, that is, there are arbitrarily large primes.

Answer 4

Let $F_n=2^{2^n}+1$ be the sequence of Fermat numbers. It is relatively easy to show that, for distinct $i,j$ we have $\gcd(F_i,F_j)=1$. Therefore, if we let $p_n$ be a sequence of primes such that $p_n$ divides $F_n$ (which is possible, since every number has at least one prime divisor), then each $p_n$ is distinct (since $p_n>1=\gcd(F_i,F_j)$), and there are infinitely many of them.

Answer 5

Here is a proof that uses a bit of group theory.

We show that, if $p$ is prime, then $2^p-1$ is divisible by a prime $q \gt p$.

Suppose that $q$ divides $2^p - 1$. Consider the multipicative group $\mathbb Z_q \setminus \{0\}$. Since $q$ divides $2^p-1$, the element $2$ has order $p$ in $\mathbb Z_q \setminus \{0\}$. Since this group has order $q-1$, by Lagrange's Theorem we have $p$ divides $q-1$. Therefore $p \lt q$.