Teorema Euclid

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.

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:

Bukti Euler

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

\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}</math>

Dengan menggunakan rumus deret geometrik beserta sifat distributif, maka $$\begin{array}{cc}\prod _{p\text{prima}}\frac{1}{1-\frac{1}{p}}& =\prod _{p\text{prima}}(1+\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\frac{1}{p^4}+\dots )\\ & =(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+\dots )\times \\ & \phantom{=,}(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}+\frac{1}{3^4}+\dots )\times \\ & \phantom{=,}(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3}+\frac{1}{5^4}+\dots )\times \\ & \phantom{=,}(1+\frac{1}{7}+\frac{1}{7^2}+\frac{1}{7^3}+\frac{1}{7^4}+\dots )\times \dots \\ & =1+\frac{1}{2}+\frac{1}{3}+\frac{1}{2^2}+\frac{1}{5}+\frac{1}{2\cdot 3}+\dots \\ & =\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n}\end{array}$$

Saat menjabarkan darab dari deret takhingga pada baris kedua, hasil penjabarannya ialah faktorisasi prima dari $\frac{1}{n}$. Berdasarkan teorema dasar aritmetika, maka setiap bilangan asli $n$ selain 1 akan memiliki faktorisasi prima yang bersifat tunggal. Akibatnya, setiap $\frac{1}{n}$ akan muncul tepat satu kali, sehingga dapat disimpulkan bahwa $$\prod _{p\text{prima}}\frac{1}{1-\frac{1}{p}}=\sum _{n=1}^{\mathrm{\infty }}\frac{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 inibahwa hanya terdapat berhingga banyaknya bilangan primatidaklah benar, sehingga dapat disimpulkan bahwa banyaknya bilangan prima adalah takhingga.}}

= \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}</math>

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 $[1,N]$ daripada banyaknya bilangan persegi pada selang yang sama. }}

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

$$\sum _{p\text{prima}}\frac{1}{p}$$

bersifat divergen.

Bukti Erdős

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

Bukti Furstenberg

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

</math> 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 menggunakan rumus Legendre

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

p^{f(p, \, n)}</math>

dengan $$f(p,n)=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\dots$$

Perhatikan bahwa $$\begin{array}{cc}f(p,n)& \le \frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^2}+\frac{n}{p^3}+\dots \\ & =\frac{n}{p-1}\\ & \le n\end{array}$$ Akibatnya, $$\begin{array}{cc}f(p,n)& \le n\\ p^{f(p,n)}& \le p^n\\ \prod _{p\text{prima}}{p}^{f(p,n)}& \le \prod _{p\text{prima}}{p}^n\\ n!& \le {\left(\prod _{p\text{prima}}p\right)}^n\\ 1& \le \frac{1}{n!}{\left(\prod _{p\text{prima}}p\right)}^n\end{array}$$

Jika hanya terdapat berhingga banyaknya bilangan prima, maka $$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n!}{\left(\prod _{p\text{prima}}p\right)}^n=\underset{n\to \mathrm{\infty }}{lim}\frac{a^n}{n!}=0\text{untuk suatu konstanta}a>0$$ yang menimbulkan kontradiksi dengan pertidaksamaan $$\frac{1}{n!}{\left(\prod _{p\text{prima}}p\right)}^n\ge 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 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.

Pernyataan yang lebih kuat

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

Teorema Dirichlet mengenai 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

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

$$\underset{x\to \mathrm{\infty }}{lim}\frac{\pi (x)}{x/\ln (x)}=1$$

Dengan menggunakan notasi asimtotik, maka hasil ini dapat dinyatakan sebagai

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

Teorema bilangan prima mengakibatkan kebenaran dari teorema Euclid, sebab $\underset{x\to \mathrm{\infty }}{lim}\frac{x}{\ln x}=\mathrm{\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 (\frac{x}{2})\ge 1$ untuk setiap bilangan riil $x\ge 2$, dengan $\pi (x)$ menyatakan fungsi pencacahan bilangan primayaitu 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 $[2,3\cdot 10^6]$. Konjektur Bertrand berhasil dibuktikan oleh Chebyshev pada 1852 sehingga postulatnya juga dinamai sebagai teorema Bertrand–Chebyshev atau teorema Chebyshev.

Pranala luar

• Euclid's Elements, Buku IX, Prop. 20 (bukti Euclid, pada situs web David Joyce dari Universitas Clark)

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29587257 (2026-08-16T07:48:06Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.