Teorema Euclid

Artikel ini berisi tentang teorema mengenai takhingga banyaknya bilangan prima. Untuk teorema mengenai bilangan sempurna dan bilangan prima Mersenne, lihat Teorema Euclid–Euler. Untuk teorema mengenai keterbagian hasil-kali bilangan bulat oleh bilangan prima, lihat Lema Euclides.

Dalam teori bilangan, teorema Euclid menyatakan bahwa terdapat takhingga banyaknya bilangan prima. Pernyataan tersebut pertama kali dibuktikan oleh Euclid dalam karya miliknya, Elements. Terdapat setidaknya 200 bukti dari teorema ini.

Bukti

Bukti Euclid

Euclid memberikan bukti yang diterbitkan dalam karya Elements miliknya (Buku IX, Proposisi 20), yang akan diparafrase dalam artikel ini.

Bukti Euclid —

Diambil sembarang himpunan hingga bilangan prima $$P=\left\{p_{1},\,p_{2},\,p_{3},\,\ldots ,\,p_{n}\right\}$$ Misalkan $N$ adalah satu lebihnya dari darab semua bilangan prima pada $P$, yaitu $$N=1+p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}$$

Terdapat dua kemungkinan yang dapat terjadi :

1. Jika $N$ merupakan bilangan prima, maka terdapat setidaknya satu bilangan prima yang tidak ada pada himpunan $P$, salah satunya ialah $N$ itu sendiri.
2. Jika $N$ merupakan bilangan komposit, maka terdapat suatu faktor prima $p$ yang habis membagi $N$. Jika $p$ merupakan anggota dari $P$, maka $p$ habis membagi $p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}$. Oleh karena $p$ habis membagi $N$ dan $p$ habis membagi $p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots \cdot p_{n}$, maka $p$ habis membagi selisih dari dua bilangan tersebut, yaitu $1$. Oleh karena tidak ada bilangan prima yang habis membagi 1, maka $p$ bukanlah anggota dari $P$. Akibatnya, terdapat setidaknya satu bilangan prima yang tidak ada pada himpunan $P$, salah satunya ialah $p$ itu sendiri.

Berdasarkan kedua kasus di atas, maka dapat disimpulkan bahwa untuk setiap himpunan berhingga bilangan prima, terdapat suatu bilangan prima yang tidak termuat pada himpunan tersebut.

Pada karya orisinalnya, Euclid menulis sembarang himpunan berhingga bilangan prima sebagai $A$, $B$, $\Gamma$

Variasi

Terdapat beberapa variasi dari bukti Euclid, salah satunya ialah sebagai berikut:

Variasi dari bukti Euclid —

Berdasarkan definisi dari faktorial, maka bilangan $n!$ habis dibagi oleh setiap bilangan asli dari $2$ sampai dengan $n$, sebab $n!$ merupakan hasil kali dari mereka semua. Akibatnya, bilangan $n!+1$ tidak habis dibagi oleh sembarang bilangan asli dari $2$ sampai dengan $n$, sehingga $n!+1$ dapat berupa bilangan prima, atau habis dibagi oleh suatu bilangan prima yang lebih dari $n$. Dalam kedua kasus tersebut, maka untuk setiap bilangan asli $n$, terdapat setidaknya satu bilangan prima yang lebih dari $n$, sehingga dapat disimpulkan bahwa banyaknya bilangan prima ialah takhingga.

Bukti Euler

Bukti dari matematikawan Swiss Leonhard Euler mengandalkan teorema dasar aritmetika, yaitu setiap bilangan asli selain 1 memiliki faktorisasi prima yang bersifat tunggal.

Bukti Euler —

Pandang darab berikut

$$\prod _{p\;{\text{prima}}}{\dfrac {1}{1-{\tfrac {1}{p}}}}=\prod _{p\;{\text{prima}}}{\dfrac {p}{p-1}}={\dfrac {2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot \ldots }{1\cdot 2\cdot 4\cdot 6\cdot 10\cdot 12\cdot 16\cdot 18\cdot 22\cdot \ldots }}$$

Dengan menggunakan rumus deret geometrik beserta sifat distributif, maka $${\begin{aligned}\prod _{p\;{\text{prima}}}{\dfrac {1}{1-{\tfrac {1}{p}}}}&=\prod _{p\;{\text{prima}}}\left(1+{\dfrac {1}{p}}+{\dfrac {1}{p^{2}}}+{\dfrac {1}{p^{3}}}+{\dfrac {1}{p^{4}}}+\ldots \right)\\&=\left(1+{\dfrac {1}{2}}+{\dfrac {1}{2^{2}}}+{\dfrac {1}{2^{3}}}+{\dfrac {1}{2^{4}}}+\ldots \right)\;\times \\&{\phantom {=,}}\left(1+{\dfrac {1}{3}}+{\dfrac {1}{3^{2}}}+{\dfrac {1}{3^{3}}}+{\dfrac {1}{3^{4}}}+\ldots \right)\;\times \\&{\phantom {=,}}\left(1+{\dfrac {1}{5}}+{\dfrac {1}{5^{2}}}+{\dfrac {1}{5^{3}}}+{\dfrac {1}{5^{4}}}+\ldots \right)\;\times \\&{\phantom {=,}}\left(1+{\dfrac {1}{7}}+{\dfrac {1}{7^{2}}}+{\dfrac {1}{7^{3}}}+{\dfrac {1}{7^{4}}}+\ldots \right)\;\times \;\ldots \\&=1+{\dfrac {1}{2}}+{\dfrac {1}{3}}+{\dfrac {1}{2^{2}}}+{\dfrac {1}{5}}+{\dfrac {1}{2\cdot 3}}+\ldots \\&=\sum _{n\,=\,1}^{\infty }{\dfrac {1}{n}}\end{aligned}}$$

Saat menjabarkan darab dari deret takhingga pada baris kedua, hasil penjabarannya ialah faktorisasi prima dari ${\tfrac {1}{n}}$. Berdasarkan teorema dasar aritmetika, maka setiap bilangan asli $n$ selain 1 akan memiliki faktorisasi prima yang bersifat tunggal. Akibatnya, setiap ${\tfrac {1}{n}}$ akan muncul tepat satu kali, sehingga dapat disimpulkan bahwa $$\prod _{p\;{\text{prima}}}{\dfrac {1}{1-{\tfrac {1}{p}}}}=\sum _{n\,=\,1}^{\infty }{\dfrac {1}{n}}$$ yang dikenal sebagai rumus darab Euler untuk fungsi zeta Riemann.

Andaikan hanya terdapat berhingga banyaknya bilangan prima, maka hasil darab pada ruas kiri memiliki nilai yang berhingga. Akan tetapi, telah dibuktikan sebelumnya bahwa deret pada ruas kanan bersifat divergen. Oleh karena terjadi kontradiksi, maka asumsi di awal paragraf ini—bahwa hanya terdapat berhingga banyaknya bilangan prima—tidaklah benar, sehingga dapat disimpulkan bahwa banyaknya bilangan prima adalah takhingga.

Akibat —

Oleh karena darab takhingga

$$\prod _{n\,=\,2}^{\infty }{\dfrac {1}{1-{\tfrac {1}{n^{2}}}}}=\prod _{n\,=\,2}^{\infty }{\dfrac {n^{2}}{n^{2}-1}}={\dfrac {4\cdot 9\cdot 16\cdot 25\cdot 36\cdot \ldots }{3\cdot 8\cdot 15\cdot 24\cdot 35\cdot \ldots }}$$

konvergen ke bilangan 2, maka terdapat lebih banyak bilangan prima daripada bilangan persegi. Dengan kata lain, untuk bilangan asli $N$ yang cukup besar, terdapat lebih banyak bilangan prima pada selang $\left[1,\,N\right]$ daripada banyaknya bilangan persegi pada selang yang sama.

Pada paper yang sama, Euler menggunakan persamaan $$\prod _{p\;{\text{prima}}}{\dfrac {1}{1-{\tfrac {1}{p}}}}=\sum _{n\,=\,1}^{\infty }{\dfrac {1}{n}}$$ untuk membuktikan teorema yang jauh lebih kuat dan belum diketahui sebelum Euler, yaitu deret

$$\sum _{p\;{\text{prima}}}{\dfrac {1}{p}}$$

bersifat divergen.

Bukti Erdős

Paul Erdős memberikan bukti yang juga bergantung pada teorema dasar aritmetika.

Bukti Erdős —

Perhatikan bahwa setiap bilangan asli selain 1 dapat difaktorkan secara tunggal menjadi hasil kali dari bilangan bulat bebas kuadrat $a$ dan bilangan persegi $b^{2}$. Misalnya, $75.600=2^{4}\cdot 3^{3}\cdot 5^{2}\cdot 7^{1}=21\cdot 60^{2}$.

Misalkan $N$ adalah bilangan asli dan $k$ menyatakan banyaknya bilangan prima yang kurang dari atau sama dengan $N$, maka bilangan-bilangan prima tersebut dapat dinyatakan sebagai $p_{1}$, $p_{2}$, $p_{3}$, sampai dengan $p_{k}$. Telah diketahui sebelumnya bahwa setiap bilangan asli $n\leq N$ dapat dinyatakan sebagai $${\begin{aligned}n&=ab^{2}\\&=\left(p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\cdot \ldots \cdot p_{k}^{e_{k}}\right)b^{2}\end{aligned}}$$ dengan $e_{i}\in \left\{0,\,1\right\}$ untuk setiap $i\in \left\{1,\,2,\,3,\,\ldots ,\,k\right\}$. Berdasarkan persamaan di atas, maka untuk setiap nilai $b$ yang tetap, terdapat paling banyak $2^{k}$ kemungkinan nilai $a$ yang dapat dibentuk. Oleh karena $a\geq 1$, maka $${\begin{aligned}n&\leq N\\ab^{2}&\leq N\\b^{2}\leq ab^{2}&\leq N\\b^{2}&\leq N\end{aligned}}$$ sehingga banyaknya nilai yang mungkin untuk $b$ tidak lebih dari ${\sqrt {N}}$. Akibatnya, untuk setiap $N\in \mathbb {N}$, terdapat paling banyak $2^{k}{\sqrt {N}}$ bilangan yang nilainya kurang dari atau sama dengan $N$. Akan tetapi, jelas bahwa terdapat $N$ bilangan yang nilainya kurang dari atau sama dengan $N$. Dengan kata lain, berlaku pertidaksamaan

$${\begin{aligned}N&\leq 2^{k}{\sqrt {N}}\\{\sqrt {N}}&\leq 2^{k}\\^{2}\!\log({\sqrt {N}})&\leq k\\{\dfrac {1}{2}}\cdot \,^{2}\!\log N&\leq k\end{aligned}}$$

yang berarti bahwa banyaknya bilangan prima yang kurang dari atau sama dengan $N$ itu paling sedikit ${\frac {1}{2}}\cdot \,^{2}\!\log N$ bilangan. Oleh karena $N$ adalah sembarang bilangan asli, maka nilai $k$ dapat sebesar yang diinginkan dengan memilih nilai $N$ yang sesuai.

Bukti Furstenberg

Artikel utama: Bukti Furstenberg mengenai takhingga banyaknya bilangan prima

Pada tahun 1955, Hillel Furstenberg memberikan pembuktian melalui kontradiksi menggunakan topologi umum.

Bukti Furstenberg —

Didefinisikan topologi pada himpunan bilangan bulat $\mathbb {Z}$—yang dikenal sebagai topologi bilangan bulat berjarak sama—dengan mendefinisikan suatu himpunan $H\subseteq \mathbb {Z}$ sebagai himpunan terbuka jika dan hanya jika $H=\varnothing$ atau $H$ dapat dinyatakan sebagai gabungan dari barisan aritmetika $a\mathbb {Z} +b$, yaitu

$$a\mathbb {Z} +b=\left\{an+b\mid n\in \mathbb {Z} \right\}$$

dengan $a\neq 0$. Oleh karena $\mathbb {Z}$ merupakan himpunan takhingga, maka setiap himpunan terbuka pada topologi ini merupakan himpunan takhingga. Dengan kata lain, setiap himpunan hingga bukanlah himpunan terbuka. Telah dibuktikan sebelumnya bahwa setiap basis $a\mathbb {Z} +b$ merupakan himpunan terbuka sekaligus tertutup. Pandang himpunan berikut:

$$S=\mathbb {Z} \setminus \left\{-1,1\right\}=\bigcup _{p\,\in \,P}p\mathbb {Z}$$

dengan $P$ menyatakan himpunan semua bilangan prima. Andaikan $P$ merupakan himpunan hingga, perhatikan bahwa

1. himpunan $S$ merupakan gabungan berhingga dari himpunan tertutup. Akibatnya, $S$ merupakan himpunan tertutup.
2. himpunan $S^{\textsf {c}}$ merupakan himpunan hingga. Akibatnya, $S$ bukan merupakan himpunan tertutup.

Oleh karena terjadi kontradiksi, maka asumsi bahwa $P$ merupakan himpunan hingga bernilai salah, sehingga $P$ haruslah himpunan takhingga.

Bukti menggunakan prinsip inklusi–eksklusi

Pada tahun 2009, Juan Pablo Pinasco memberikan pembuktian melalui kontradiksi menggunakan prinsip inklusi–eksklusi.

Bukti Pinasco —

Misalkan $p_{1}<p_{2}<\ldots <p_{n}$ menyatakan $n$ bilangan prima terkecil. Untuk setiap $N\in \mathbb {N}$, perhatikan bahwa banyaknya bilangan asli pada selang $\left[1,\,N\right]$ yang habis dibagi oleh $p_{i}$ ialah $\left\lfloor {\tfrac {N}{p_{i}}}\right\rfloor$, dengan $\left\lfloor \cdot \right\rfloor$ menyatakan fungsi lantai. Dengan menerapkan tapis Eratosthenes menggunakan prinsip inklusi–eksklusi, maka banyaknya bilangan asli pada selang $\left[1,\,N\right]$ dapat dihitung melalui dua cara berbeda, sehingga didapatkan persamaan $${\begin{aligned}N-1&=\sum _{i\,=\,1}^{n}\left\lfloor {\dfrac {N}{p_{i}}}\right\rfloor -\sum _{i\,<\,j}\left\lfloor {\dfrac {N}{p_{i}p_{j}}}\right\rfloor \\&{\phantom {\sum }}+\sum _{i\,<\,j\,<\,k}\left\lfloor {\dfrac {N}{p_{i}p_{j}p_{k}}}\right\rfloor -\ldots \pm (-1)^{n+1}\left\lfloor {\dfrac {N}{p_{1}p_{2}\ldots p_{n}}}\right\rfloor \\1-{\dfrac {1}{N}}&=\sum _{i\,=\,1}^{n}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}}}\right\rfloor -\sum _{i\,<\,j}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}p_{j}}}\right\rfloor \\&{\phantom {\sum }}+\sum _{i\,<\,j\,<\,k}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}p_{j}p_{k}}}\right\rfloor -\ldots \pm (-1)^{n+1}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{1}p_{2}\ldots p_{n}}}\right\rfloor \end{aligned}}$$

Dengan menggunakan teorema apit, maka

$$\lim _{N\,\to \,\infty }{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}}}\right\rfloor ={\dfrac {1}{p_{i}}}$$

sehingga

$${\begin{aligned}1-{\dfrac {1}{N}}&=\sum _{i\,=\,1}^{n}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}}}\right\rfloor -\sum _{i\,<\,j}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}p_{j}}}\right\rfloor \\&{\phantom {\sum }}+\sum _{i\,<\,j\,<\,k}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}p_{j}p_{k}}}\right\rfloor -\ldots \pm (-1)^{n+1}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{1}p_{2}\ldots p_{n}}}\right\rfloor \\\lim _{N\,\to \,\infty }1-{\dfrac {1}{N}}&=\lim _{N\,\to \,\infty }\sum _{i\,=\,1}^{n}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}}}\right\rfloor -\sum _{i\,<\,j}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}p_{j}}}\right\rfloor \\&{\phantom {\sum }}+\sum _{i\,<\,j\,<\,k}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{i}p_{j}p_{k}}}\right\rfloor -\ldots \pm (-1)^{n+1}{\dfrac {1}{N}}\left\lfloor {\dfrac {N}{p_{1}p_{2}\ldots p_{n}}}\right\rfloor \\1&=\sum _{i}{\dfrac {1}{p_{i}}}-\sum _{i\,<\,j}{\dfrac {1}{p_{i}p_{j}}}+\sum _{i\,<\,j\,<\,k}{\dfrac {N}{p_{i}p_{j}p_{k}}}-\ldots \pm (-1)^{n+1}{\dfrac {1}{p_{1}p_{2}\ldots p_{n}}}\\0&=1-\sum _{i}{\dfrac {1}{p_{i}}}+\sum _{i\,<\,j}{\dfrac {1}{p_{i}p_{j}}}-\sum _{i\,<\,j\,<\,k}{\dfrac {N}{p_{i}p_{j}p_{k}}}+\ldots \pm (-1)^{n}{\dfrac {1}{p_{1}p_{2}\ldots p_{n}}}\\&=\prod _{i}\left(1-{\dfrac {1}{p_{i}}}\right)\end{aligned}}$$

Jika tidak ada bilangan prima selain $p_{1}$ sampai dengan $p_{n}$, maka hasil kali di atas tidak mungkin bernilai nol. Akibatnya, terdapat bilangan prima selain $p_{1}$ sampai dengan $p_{n}$.

Bukti menggunakan rumus Legendre

Pada tahun 2010, Junho Peter Whang menerbitkan pembuktian melalui kontradiksi menggunakan rumus Legendre.

Bukti Whang —

Misalkan $n$ adalah bilangan asli. Berdasarkan rumus Legendre (atau terkadang diatributkan sebagai rumus de Polignac), maka $$n!=\prod _{p\;{\text{prima}}}p^{f(p,\,n)}$$ dengan $$f(p,\,n)=\left\lfloor {\dfrac {n}{p}}\right\rfloor +\left\lfloor {\dfrac {n}{p^{2}}}\right\rfloor +\left\lfloor {\dfrac {n}{p^{3}}}\right\rfloor +\ldots$$

Perhatikan bahwa $${\begin{aligned}f(p,\,n)&\leq {\dfrac {n}{p}}+{\dfrac {n}{p^{2}}}+{\dfrac {n}{p^{2}}}+{\dfrac {n}{p^{3}}}+\ldots \\&={\dfrac {n}{p-1}}\\&\leq n\end{aligned}}$$ Akibatnya, $${\begin{aligned}f(p,\,n)&\leq n\\p^{f(p,\,n)}&\leq p^{n}\\\prod _{p\;{\text{prima}}}p^{f(p,\,n)}&\leq \prod _{p\;{\text{prima}}}p^{n}\\n!&\leq \left(\prod _{p\;{\text{prima}}}p\right)^{n}\\1&\leq {\dfrac {1}{n!}}\left(\prod _{p\;{\text{prima}}}p\right)^{n}\end{aligned}}$$

Jika hanya terdapat berhingga banyaknya bilangan prima, maka $$\lim _{n\,\to \,\infty }{\dfrac {1}{n!}}\left(\prod _{p\;{\text{prima}}}p\right)^{n}=\lim _{n\,\to \,\infty }{\dfrac {a^{n}}{n!}}=0\qquad \qquad {\text{untuk suatu konstanta}}\;a>0$$ yang menimbulkan kontradiksi dengan pertidaksamaan $${\dfrac {1}{n!}}\left(\prod _{p\;{\text{prima}}}p\right)^{n}\geq 1$$ yang berlaku untuk setiap $n\in \mathbb {N}$.

Pembuktian melalui kontruksi

Filip Saidak memberikan pembuktian melalui konstruksi, yang tidak menggunakan reductio ad absurdum maupun lema Euclides (yaitu, jika bilangan prima $p$ habis membagi $ab$, maka $p$ habis membagi $a$ atau $p$ habis membagi $b$).

Bukti Saidak —

Berdasarkan teorema dasar aritmetika, maka setiap bilangan asli yang lebih dari 1 akan memiliki setidaknya 1 faktor prima. Oleh karena setiap dua bilangan asli berurutan (yaitu $n$ dan $n+1$) tidak memiliki faktor persekutuan selain 1, maka bilangan $n(n+1)$ memiliki faktor prima berbeda yang lebih banyak daripada faktor prima dari $n$ itu sendiri. Akibatnya, rantai bilangan pronik

$$n_{i+1}=n_{i}(n_{i}+1)\qquad \qquad n_{1}=1$$

$${\begin{array}{|c|c|c|c|}\hline \;i\;&n&n(n+1)&p\mid (n(n+1))\\\hline 1&1&2&\left\{2\right\}\\2&2&6&\left\{2,\,3\right\}\\3&6&42&\left\{2,\,3,\,7\right\}\\4&42&1806&\left\{2,\,3,\,7,\,43\right\}\\5&1806&3263442&\left\{2,\,3,\,7,\,43,\,13,\,139\right\}\\\vdots &\vdots &\vdots &\vdots \end{array}}$$

dapat dipandang sebagai suatu barisan himpunan bilangan prima yang terus bertambah tanpa batas.

Bukti menggunakan argumen ganjil-genap

Romeo Meštrović menggunakan argumen ganjil-genap untuk menunjukkan bahwa jika banyaknya bilangan prima itu berhingga, maka 3 adalah bilangan prima terbesar.

Bukti Meštrović —

Misalkan $2<3<5<7<\ldots <p_{n}$ merupakan semua bilangan prima. Pandang bilangan $$P_{1}=3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}$$

Perhatikan bahwa semua bilangan yang bersifat relatif prima dengan $P_{1}$ merupakan anggota dari himpunan $$H_{1}=\left\{1,\,2,\,4,\,8,\,16,\,32,\,\ldots \right\}$$ Oleh karena

1. $\operatorname {FPB} (2,\,P_{1})=1$, maka $\operatorname {FPB} (P_{1}-2,\,P_{1})=1$. Akibatnya, $P_{1}-2\in H_{1}$.
2. $\operatorname {FPB} (2,\,P_{1})=1$, maka $P_{1}$ merupakan bilangan ganjil. Akibatnya, $P_{1}-2$ juga merupakan bilangan ganjil.

Berdasarkan kedua informasi di atas, maka dapat disimpulkan bahwa

$$P_{1}-2=1$$

Akan tetapi,

$${\begin{aligned}3\cdot 5\cdot 7\cdot \ldots \cdot p_{n}&>3\cdot 1\cdot 1\cdot \ldots \cdot p_{n}\\P_{1}&>3p_{n}\\P_{1}-2&>3p_{n}-2\\1&>3p_{n}-2>3-2\\1&>1\end{aligned}}$$

yang jelas menimbulkan kontradiksi.

Catatan —

Bukti Meštrović tetap berlaku meskipun bilangan prima $2$ diganti dengan sembarang bilangan prima $p_{k}$, dengan $k\in \left\{2,\,3,\,\ldots ,\,n-1\right\}$. Dalam kasus ini, pandang bilangan $$P_{k}=\prod _{i\,=\,1 \atop i\,\neq \,k}^{n}p_{i}$$

Perhatikan bahwa semua bilangan yang bersifat relatif prima dengan $P_{k}$ merupakan anggota dari himpunan $$H_{k}=\left\{1,\,p_{k},\,\left(p_{k}\right)^{2},\,\left(p_{k}\right)^{3},\,\left(p_{k}\right)^{4},\,\left(p_{k}\right)^{5},\,\ldots \right\}$$ Oleh karena

1. $\operatorname {FPB} (p_{k},\,P_{k})=1$, maka $\operatorname {FPB} (P_{k}-p_{k},\,P_{k})=1$. Akibatnya, $P_{k}-p_{k}\in H_{k}$.
2. $\operatorname {FPB} (p_{k},\,P_{k})=1$, maka $p_{k}\not \mid P_{k}$. Akibatnya, $p_{k}\not \mid (P_{k}-p_{k})$.

Berdasarkan kedua informasi di atas, maka dapat disimpulkan bahwa

$$P_{k}-p_{k}=1$$

Akan tetapi,

$${\begin{aligned}{\dfrac {1}{p_{k}}}\cdot 2\cdot 3\cdot 5\cdot \ldots \cdot p_{n}&>2\cdot 1\cdot 1\cdot \ldots \cdot p_{n}\\P_{k}&>2p_{n}\\P_{k}-p_{k}&>2p_{n}-p_{k}\\1&>2p_{n}-p_{k}>p_{k}\\1&>p_{k}\end{aligned}}$$

yang jelas menimbulkan kontradiksi.

Pernyataan yang lebih kuat

Teorema-teorema pada bagian ini mengakibatkan kebenaran teorema Euclid (beserta hasil-hasil lainnya).

Teorema Dirichlet mengenai barisan aritmetika

Artikel utama: Teorema Dirichlet (barisan aritmetika)

Teorema Dirichlet menyatakan bahwa untuk setiap dua bilangan asli $a$ dan $b$ yang saling prima, terdapat takhingga banyaknya bilangan prima dengan bentuk umum $a+nb$, dengan $n$ adalah suatu bilangan asli. Dengan kata lain, terdapat takhingga banyaknya bilangan prima yang kongruen dengan $a$ modulo $b$.

Teorema bilangan prima

Artikel utama: Teorema bilangan prima

Misalkan $\pi (x)$ menyatakan fungsi pencacahan bilangan prima—yang memberikan banyaknya bilangan prima yang kurang dari atau sama dengan $x$—untuk setiap bilangan riil $x$. Teorema bilangan prima menyatakan bahwa fungsi ${\tfrac {x}{\ln(x)}}$ merupakan hampiran yang bagus untuk $\pi (x)$, dalam artian bahwa limit dari hasil bagi dari dua fungsi $\pi (x)$ dan ${\tfrac {x}{\ln(x)}}$ saat nilai $x$ meningkat tanpa batas ialah $1$. Secara simbolis, maka

$$\lim _{x\,\to \,\infty }{\dfrac {\pi (x)}{x/\ln(x)}}=1$$

Dengan menggunakan notasi asimtotik, maka hasil ini dapat dinyatakan sebagai

$$\pi (x)\sim {\dfrac {x}{\ln x}}$$

Teorema bilangan prima mengakibatkan kebenaran dari teorema Euclid, sebab $\displaystyle \lim _{x\,\to \,\infty }{\dfrac {x}{\ln x}}=\infty$.

Teorema Bertrand–Chebyshev

Dalam teori bilangan, postulat Bertrand adalah teorema yang menyatakan bahwa untuk setiap bilangan asli $n$, terdapat setidaknya satu bilangan prima $p$ sedemikian sehingga $$n<p<2n$$ Hal ini ekuivalen dengan pernyataan bahwa $\pi (x)-\pi ({\tfrac {x}{2}})\geq 1$ untuk setiap bilangan riil $x\geq 2$, dengan $\pi (x)$ menyatakan fungsi pencacahan bilangan prima—yaitu banyaknya bilangan prima yang nilainya kurang dari atau sama dengan $x$.

Pernyataan ini pertama kali dikonjekturkan pada tahun 1845 oleh Joseph Bertrand. Bertrand sendiri memverifikasi pernyataan tersebut untuk setiap bilangan pada selang $\left[2,\,3\cdot 10^{6}\right]$. Konjektur Bertrand berhasil dibuktikan oleh Chebyshev pada 1852 sehingga postulatnya juga dinamai sebagai teorema Bertrand–Chebyshev atau teorema Chebyshev.

Pranala luar

• (Inggris) Weisstein, Eric W. "Euclid's Theorem". MathWorld.
• (Inggris) Euclid's Elements, Buku IX, Prop. 20 (bukti Euclid, pada situs web David Joyce dari Universitas Clark)