# Tag Archives: prime numbers

## The infinitude of the primes

As we all know, a (natural) number $p>1$ is called prime if its positive divisors are only $1$ and $p$. The fact that prime numbers are infinite in number was proved by Euclid (although it is not clear whether he discovered it) and the proof is a little gem of mathematical reasoning. We present his proof below:

Theorem: There are infinitely many prime numbers.

Proof: Consider any list of prime numbers, say $p_1,p_2\cdots p_n$. The number $P=p_1p_2\cdots p_n+1$ is clearly not on the list. If $P$ is not prime, then by definition there is a prime number $p$ which divides $P$. Clearly $p\ne p_i$ for any $i$ as otherwise $p$ divides $1$, a contradiction.  So $p$ is a prime number not on the list. If, on the other hand, $P$ is prime, then it is anyway a prime number not on the list. Hence our list is incomplete.$\Box$

We now give another beautiful proof for the same theorem owing to Euler. Although it does not strictly qualify as a valid mathematical proof by modern standards and is really nothing more then heuristic reasoning yet its “wow factor” is so high that as an exception it is still referred to as a proof. It can be recast into a more rigorous form but we do not so here so that its original taste is not disturbed. The essential argument here is that if the primes were finite then the product $\prod_{\text{p prime}}\frac{1}{1-1/p}$ would be finite which is not the case.

Theorem: There are infinitely many prime numbers.

Proof: Let $P$ denote the set of all primes. Now consider the product $\prod_{p\in P}\frac{1}{1-1/p}$ i.e.

$(\frac{1}{1-1/2})(\frac{1}{1-1/3})(\frac{1}{1-1/5})\cdots\\\\=(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\cdots)(1+\frac{1}{3}+\frac{1}{9}+\frac{1}{27}\cdots)(1+\frac{1}{5}+\frac{1}{25}+\frac{1}{125}\cdots)\cdots$

by the formula of the geometric series.

Next we observe that if we multiply out the terms (assuming such a multiplication is valid) then the reciprocal of every positive integer will occur exactly once by the uniqueness of the fundamental theorem of arithmetic. If $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is the unique factorization of $n$ then $\frac{1}{n}$ would result in the multiplication only when $\frac{1}{p_1^{\alpha_1}},\cdots \frac{1}{p_k^{\alpha_k}}$ are multiplied. Hence the above product

$\prod_{p\in P}\frac{1}{1-1/p}=\sum_{n=1}^\infty \frac{1}{n}$. The latter harmonic series is well known to be divergent. Hence there must be infinitely many terms in $P$.$\Box$