Main Page

From ProofWiki
Jump to: navigation, search

Welcome to $\mathsf{Pr} \infty \mathsf{fWiki}$


ProofWiki is an online compendium of mathematical proofs! Our goal is the collection, collaboration and classification of mathematical proofs. If you are interested in helping create an online resource for math proofs feel free to register for an account. Thanks and enjoy!

If you have any questions, comments, or suggestions please post on the discussion page, or contact one of the administrators. Also, feel free to take a look at the frequently asked questions because you may not be the first with your idea.

To see what's currently happening in the community, visit the community portal.

14,813 Proofs 12,610 Definitions Help

Featured Proof

Number of Primes is Infinite


The number of primes is infinite.

Proof 1

Euclid's Theorem states that:

For any finite set of prime numbers, there exists a prime number not in that set.

The result follows by corollary.


Proof 2

Define a topology on the integers $\Z$ by declaring a subset $U \subseteq \Z$ to be an open set if and only if it is either:

the empty set $\varnothing$


a union of sequences $S \left({a, b}\right)$, where:
$S \left({a, b}\right) = \left\{{a n + b: n \in \Z}\right\} = a \Z + b$

In other words, $U$ is open if and only if every $x \in U$ admits some non-zero integer $a$ such that $S \left({a, x}\right) \subseteq U$.

The open set axioms are easily verified:

$(O1): \quad$ Any union of open sets is open:

For any set of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $S \left({a_i, x}\right) \subseteq U_i$ also shows that $S \left({a_i, x}\right) \subseteq U$.

$(O2): \quad$ The intersection of two (and hence finitely many) open sets is open:

Let $U_1$ and $U_2$ be open sets and let $x \in U_1 \cap U_2$ (with numbers $a_1$ and $a_2$ establishing membership).

Set $a$ to be the lowest common multiple of $a_1$ and $a_2$.


$S \left({a, x}\right) \subseteq S \left({a_i, x}\right) \subseteq U_1 \cap U_2$

$(O3): \quad$ By definition, $\varnothing$ is open: $\Z$ is just the sequence $S \left({1, 0}\right)$, and so is open as well.

The topology is quite different from the usual Euclidean one, and has two notable properties:

  1. Since any non-empty open set contains an infinite sequence, no finite set can be open. Put another way, the complement of a finite set cannot be a closed set.
  2. The basis sets $S \left({a, b}\right)$ are both open and closed: they are open by definition, and we can write $S \left({a, b}\right)$ as the complement of an open set as follows:
$\displaystyle S \left({a, b}\right) = \Z \setminus \bigcup_{j \mathop = 1}^{a - 1} S(a, b + j)$.

The only integers that are not integer multiples of prime numbers are $-1$ and $+1$, that is:

$\displaystyle \Z \setminus \left\{{-1, + 1}\right\} = \bigcup_{p \ \text{prime}} S \left({p, 0}\right)$

By the first property, the set on the left-hand side cannot be closed.

On the other hand, by the second property, the sets $S \left({p, 0}\right)$ are closed.

So, if there were only finitely many prime numbers, then the set on the right-hand side would be a finite union of closed sets, and hence closed.

Therefore by Proof by Contradiction, there must be infinitely many prime numbers.


Proof 3

Aiming for a contradiction, suppose that there are only $N$ prime numbers.

Let the set of all primes be:

$\Bbb P = \left\{{p_1, p_2, \ldots, p_N}\right\}$

By the Fundamental Theorem of Arithmetic, every integer $n > 1$ can be expressed in the form:

$n = {p_1}^{a_1} {p_2}^{a_2} \dotsm {p_n}^{a_n}$

Let $a$ be the largest of the indices.


$\displaystyle \sum_{k \mathop = 1}^n \frac 1 k \le \prod_{j \mathop = 1}^N \left({\sum_{k \mathop = 0}^a \frac 1 { {p_j}^k} }\right)$

expressible in the form:

\((1):\quad\) \(\displaystyle 1 + \frac 1 2 + \frac 1 3 + \dotsb + \frac 1 n\) \(\le\) \(\displaystyle \left({1 + \frac 1 {p_1} + \frac 1 { {p_1}^2} + \dotsb + \frac 1 { {p_1}^n} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\displaystyle +\) \(\displaystyle \left({1 + \frac 1 {p_2} + \frac 1 { {p_2}^2} + \dotsb + \frac 1 { {p_2}^n} }\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\displaystyle +\) \(\displaystyle \ \dotsb\) $\quad$ $\quad$
\(\displaystyle \) \(\) \(\displaystyle +\) \(\displaystyle \left({1 + \frac 1 {p_N} + \frac 1 { {p_N}^2} + \dotsb + \frac 1 { {p_N}^n} }\right)\) $\quad$ $\quad$

which can be seen by multiplying out the factors on the right hand side

But from Sum of Infinite Geometric Progression:

$1 + x + x^2 + \dotsb = \dfrac 1 {1 - x}$

for all $x$ such that $\left\vert{x}\right\vert < 1$.

Thus the factors in $(1)$ are less than the numbers:

$\dfrac 1 {1 - 1 / p_1}, \dfrac 1 {1 - 1 / p_2}, \dotsb, \dfrac 1 {1 - 1 / p_N}$

and so:

$1 + \dfrac 1 2 + \dfrac 1 3 + \dotsb + \dfrac 1 n < \dfrac {p_1} {p_1 - 1} \dfrac {p_2} {p_2 - 1} \dotsm \dfrac {p_N} {p_N - 1}$

for every $n$.

This contradicts the result Sum of Reciprocals is Divergent.

Hence the result, by Proof by Contradiction.


Proof 4

Aiming for a contradiction, suppose there exist only a finite number of primes.

From Euler Product for Riemann Zeta Function:

$\displaystyle \sum_{n \mathop \ge 1} \dfrac 1 {n^z} = \prod_p \frac 1 {1 - p^{-z}}$

When $z = 1$ this gives:

$\displaystyle \sum_{n \mathop \ge 1} \dfrac 1 n = \prod_p \frac 1 {1 - 1/p}$

As by hypothesis there exist only a finite number of primes, the right hand side is also finite.

But from Sum of Reciprocals is Divergent, the left hand side diverges to infinity.

The result follows by Proof by Contradiction.