> [!NOTE] Theorem (Euclid) > There are are arbitrarily large [[Prime Numbers|primes]]. ###### Proof (Euclid) Fix $n\in \mathbb{N}.$ WTS there exists a prime $\geq n.$ Let $P= \{ k\in\mathbb{N} \mid k< n \text{ and } k \text{ is prime} \}.$ Let $(p_{i})_{i=0}^{k}$ be a [[List|list]] of elements of $P,$ say in order of size. Define the following natural number $N:= 1+ p_{0}\cdot p_{1} \cdot p_{2}\dots p_{k-1}$Suppose $p\in P.$ Then $N$ is [[Congruence Modulo n|congruent]] to $1$ modulo $p.$ In particular $N$ is not divisible by $p.$ Now since [[Every natural number greater than one is divisible by a prime number|every natural number greater than one is divisible by a prime number]] or by [[Integers form Unique Factorisation Domain (Fundamental Theorem of Arithmetic)|FTA]], $N$ is divisible by some prime $q.$ We deduce $q$ does not lie in $P$ and so $q\geq n.$ ###### Proof (Furstenberg) We define a curious [[Topological Spaces|topology]] of $\mathbb{Z}$: a subset $A\subset \mathbb{Z}$ is open if and only if for all $a\in A$, it contains an arithmetic progression containing $a$, that is, $a+b\mathbb{Z}\subset A$ for some $b>0$ (the empty set is vacuously open). Note here that any non-empty open set must be infinite. This topology, which we denote $\mathcal{T}$, is known as the Furstenberg topology on $\mathbb{Z}$. One can check that the Furstenberg topology satisfies: $\emptyset, \mathbb{Z}\in \mathcal{T}$; closure under arbitrary unions; and finite intersections. However, this follows simply from the fact that $\mathcal{T}$ is the topology generated by the [[Topological Bases|basis]] of arithmetic progressions with non-zero difference: $\mathcal{B} = \{ a+b \mathbb{Z} \mid a,b\in \mathbb{Z}, b\neq{0} \}$. The set $\mathcal{B}$ is indeed a topological basis as it clearly covers $\mathbb{Z}$ and the intersection of arithmetic progressions is an arithmetic progression (this is the [[Chinese Remainder Theorem|CRT]]). Furthermore, $\mathcal{T}$ is *metrizable* (see https://arxiv.org/pdf/1912.11663). Here's the crux. The fact that any natural number greater than one is divisible by a prime number can be expressed as follows: $\mathbb{Z}\setminus \{ 1,-1 \} = \bigcup_{p\in \mathbb{P}}p\mathbb{Z},$where $\mathbb{P}$ denotes the set of all primes. If $\mathbb{P}$ is finite, then the left-hand side is closed as it is a finite union of closed sets: $p\mathbb{Z}$ is closed since $p\mathbb{Z}= \mathbb{Z}\setminus\bigcup_{j=1}^{p-1}j\mathbb{Z}$ (in fact, all elements of $\mathcal{B}$ are clopen). This means that $\{ 1,-1 \}$ is open which contradicts the fact that any non-empty open set must be infinite. We conclude that $\mathbb{P}$ is infinite.