Ada berapa banyak bilangan prima?

Bilangan prima adalah bilangan asli yang hanya memiliki dua faktor, yaitu 1 dan bilangan itu sendiri. Berbeda dari bilangan komposit (non-prima), yang faktornya bisa lebih dari dua.

Prima	Komposit
\begin{aligned} 2 &= 1 \cdot 2 \\ 13 &= 1 \cdot 13 \\ 821 &= 1 \cdot 821 \\ 6043 &= 1 \cdot 6043 \\ 115249 &= 1 \cdot 115249 \\ \end{aligned}	\begin{aligned} 8 &= 1 \cdot 4 \cdot 2 \\ 24 &= 1 \cdot 2 \cdot 3 \cdot 4 \\ 648 &= 1 \cdot 4 \cdot 9 \cdot 18 \\ 1144 &= 1 \cdot 13 \cdot 88 \\ 443631 &= 1 \cdot 543 \cdot 817 \\ \end{aligned}

Kita dapat mendaftarkan bilangan prima sebanyak yang kita mau: 2, 3, 5, 7, 11, 13, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, dan seterusnya.

Namun sampai berapa banyak daftar ini bisa diteruskan? Tampaknya ada tak berhingga bilangan prima yang bisa dibuat.

Terdapat tak berhingga bilangan prima

Notasi matematika

Terdapat tak berhingga bilangan prima dapat dituliskan sebagai:

|P| = \aleph_0

Yang berarti bilangan prima dapat dinomori dengan bilangan asli (\mathbb{N}). Alef nol (\aleph_0) adalah lambang bagi banyaknya bilangan asli.

Bagaimana membuktikannya?

Tentunya kita bisa mencarinya satu per satu untuk semua kemungkinan. Namun cara ini bermasalah, karena tidak akan berhenti.

Kira-kira algoritmanya adalah seperti ini:

n menunjukkan banyaknya bilangan prima yang sejauh ini ditemukan.
Awalnya n = 0 (karena belum ditemukan)

Telusuri bilangan asli k dari 2, 3, 4, dan seterusnya:

Jika k memiliki faktor selain 1 dan k,

berarti itu adalah bilangan prima:
tambahkan n

Setelah selesai, nilai n menunjukkan banyaknya bilangan prima.

Karena kita menelusuri semua kemungkinan bilangan asli, maka algoritma ini akan berjalan terus tanpa kita tahu kapan boleh berhenti. Jika jumlah bilangan prima tak berhingga, jelas tidak akan pernah berhenti. Namun kalaupun banyaknya bilangan prima berhingga (misalnya 2 juta), algoritma ini tetap akan menguji terus bilangan yang lebih besar, siapa tahu ada bilangan prima di sana.

Dengan demikian algoritma ini undecidable, karena tidak sanggup memberikan jawaban pertanyaan kita. Namun persoalannya sendiri, yaitu, Apakah banyaknya bilangan prima adalah tak berhingga, belum tentu undecidable. Kalau saja ada algoritma atau cara membuktikan lain yang bisa memberikan jawaban bagi persoalan ini, masalah ini menjadi decidable. Ternyata memang ada.

Pembuktian

Kita akan mencoba membuktikan dengan pembuktian tak langsung, dimulai dari mengasumsikan H_0 bahwa banyaknya bilangan prima (P) sebenarnya berhingga.

\begin{aligned} H_0: |P| < \aleph_0 \end{aligned}

Kemudian kalau kita berhasil membuktikan bahwa H_0 salah, berarti yang benar adalah H_A:

\begin{aligned} H_0: |P| < \aleph_0 \\ H_A: |P| \ge \aleph_0 \end{aligned}

Jika bilangan prima terbatas, akan ada sebuah bilangan prima terbesar dalam himpunan bilangan prima, yaitu p_n.

P = \{ p_1, p_2, p_3, \ldots, p_n\}

Sekarang mari kita kalikan seluruhnya:

\begin{aligned} p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p_n = q \end{aligned}

Tentunya jelas bahwa q bukan bilangan prima, karena memiliki faktor p_1, p_2, hingga p_n. Namun bagaimana dengan q+1?

Jika q+1 prima, maka p_n bukanlah bilangan prima terbesar.
Jika q+1 bukan bilangan prima, berarti pasti faktornya bukan dari salah satu p_1, p_2, hingga p_n, karena ketika dibagi akan bersisa 1.

Jadi H_0 akan menghasilkan kontradiksi. Akibatnya, H_0 salah. Kesimpulan dari pembuktian ini adalah H_A: |P| \ge \aleph_0. Jadi terbukti bahwa banyaknya bilangan prima adalah tak berhingga.

Decidability

Pembuktian ini menunjukkan bahwa persoalan, Apakah benar bilangan prima banyaknya tak berhingga? merupakan persoalan yang decidable, dapat ditentukan benar salahnya. Walaupun ada cara pembuktian yang tak dapat berhenti, tetapi ada juga cara pembuktian yang bisa berhenti dan memunculkan jawaban.

Siapa orang pertama yang membuktikan hal ini?

Pembuktian ini pertama kali disajikan oleh Euclid dalam buku Elements, tetapi dalam bentuk pembuktian langsung.

Berikutnya: Glosarium