Bilangan prima

Bilangan prima adalah bilangan asli lebih dari 1 yang bukan hasilkali dari dua bilangan asli yang lebih kecil. Bilangan asli yang lebih dari 1 dan bukan bilangan prima disebut bilangan komposit. Misalnya, 5 adalah bilangan prima karena 5 dapat ditulis sebagai $1\times 5$ atau $5\times 1$, sedangkan 4 bukanlah bilangan prima karena hasilkalinya ($2\times 2$), dimana kedua bilangan lebih kecil dari 4. Bilangan prima merupakan bagian pusat dari teori bilangan karena melibatkan teorema dasar aritmetika: setiap bilangan asli lebih besar dari 1 adalah bilangan prima itu sendiri atau dapat difaktorkan sebagai hasil kali tunggal hingga urutannya.

Bilangan komposit dapat disusun menjadi persegi panjang, sedangkan bilangan prima tidak dapat.

Sifat-sifat yang menjadikan bilangan prima disebut primalitas. Metode sederhana namun lambat yang memeriksa primalitas untuk bilangan $n$, disebut pembagian percobaan. Metode ini menguji apakah $n$ kelipatan dari suatu bilangan bulat antara $2$ dan ${\sqrt {n}}$. Algoritma lebih cepatnya adalah uji primalitas Miller–Rabin, algoritma cepat namun memiliki kesempatan galat kecil; dan uji primalitas Agrawal–Kayal–Saxena, algoritma yang selalu memberikan solusi yang benar dalam waktu polinomial, namun sangat lambat bila dipraktekkan. Metode cepat khususnya tersedia dalam bilangan bentuk khusus, seperti bilangan Mersenne. Hingga pada Desember 2018, bilangan prima terbesar yang diketahui merupakan bilangan prima Mersenne dengan 24.862.048 digit.

Sekitar 300 SM, Euklides menjelaskan bahwa ada tak berhingga banyaknya bilangan prima. Tidak ada rumus sederhana yang memisahkan bilangan prima dari bilangan komposit. Akan tetapi, sebaran bilangan prima dalam jumlah bilangan asli yang sangat banyak dapat digambar secara statistik. Hasil pertama sebaran bilangan prima tersebut mengarah pada teorema bilangan prima, yang dibuktikan pada akhir abad ke-19. Teorema ini mengatakan bilangan terbesar yang dipilih secara acak menjadi bilangan prima berbanding terbalik dengan jumlah digitnya, yaitu logaritma.

Beberapa masalah-masalah bersejarah yang melibatkan bilangan prima masih belum terpecahkan. Masalah di antaranya konjektur Goldbach, yang menyatakan bahwa setiap bilangan bulat lebih besar dari 2 dapat dibentuk sebagai jumlah dua bilangan prima, dan konjektur bilangan prima kembar, menyatakan bahwa ada tak berhingga banyaknya pasangan bilangan prima yang memiliki sebuah bilangan genap di antaranya. Masalah-masalah tersebut mendorong pengembangan berbagai cabang dalam teori bilangan, yang fokus pada aspek bilangan analitik atau bilangan aljabar. Dalam kehidupan sehari-hari, bilangan prima dipakai dalam teknologi informasi, seperti kriptografi kunci publik, yang bergantung pada kesulitan memfaktorkan bilangan yang lebih besar menjadi faktor bilangan prima. Dalam aljabar abstrak, objek yang umumnya berperilaku sebagai bilangan prima di antaranya elemen bilangan prima dan ideal bilangan prima.

Definisi dan contoh

Bilangan asli (1, 2, 3, 4, 5, dst.) dapat dikatakan bilangan prima jika bilangan asli lebih besar dari 1 dan tidak dapat ditulis sebagai hasil kali bilangan asli yang lebih kecil. Bilangan asli yang lebih dari 1, namun bukan merupakan bilangan prima disebut bilangan komposit. Dengan kata lain, $n$ dikatakan bilangan prima jika terdapat $n$ benda tidak dapat dibagi menjadi kelompok dengan jumlah yang sama, yang terdiri dari satu benda. Bilangan prima juga diilustrasikan sebagai susunan $n$ titik menjadi persegi panjang yang lebar dan tingginya lebih dari satu titik. Misalnya, bilangan di antara 1 sampai 6, bilangan primanya adalah 2, 3, dan 5; karena tidak ada bilangan lain yang membagi ketiga bilangan tersebut tanpa adanya sisa. 1 bukan bilangan prima, karena merupakan pengecualian yang khusus dalam definisi di atas. 4 = 2 × 2 dan 6 = 2 × 3 merupakan bilangan komposit.

Gambaran melalui batang Cuisenaire bahwa 7 adalah bilangan prima. Karena 2, 3, 4, 5, atau 6 yang tidak dapat membagi 7 secara merata.

Pembagi bilangan asli $n$ adalah bilangan asli yang membagi $n$ sama rata. Pembagi pada setiap bilangan asli tersebut adalah 1 dan dirinya sendiri. Jika $n$ memiliki pembagi lain, maka $n$ bukanlah bilangan prima. Gagasan ini merujuk ke sebuah definisi bilangan prima yang berbeda namun ekuivalen: terdapat bilangan setidaknya dua pembagi bilangan positif, 1 dan dirinya sendiri. Ada cara lain untuk menjelaskan hal tersebut, yaitu: $n$ adalah bilangan prima jika $n$ lebih besar dari 1 dan tidak ada bilangan $2,3,\dots ,n-1$ yang membagi $n$ sama rata.

Berikut adalah 25 bilangan prima pertama (semua bilangan prima yang lebih kecil dari 100):

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97 (barisan A000040 pada OEIS).

Tidak ada bilangan genap $n$ yang lebih besar dari 2 adalah bilangan prima karena bilangannya dapat dibentuk sebagai hasil kali ${\textstyle 2\times {\frac {n}{2}}}$. Karena itu, setiap bilangan prima selain dari 2 adalah bilangan ganjil, dan bilangan tersebut disebut bilangan prima ganjil. Ketika ditulis dalam sistem desimal biasa dengan cara yang serupa, semua bilangan prima yang lebih besar dari 5 berakhir dengan digit satuan 1, 3, 7, atau 9. Bilangan yang berakhir dengan digit satuan yang berbeda adalah bilangan komposit: bilangan desimal yang digit satuannya adalah 0, 2, 4, 6, atau 8 adalah bilangan genap, dan bilangan desimal yang berakhir dengan digit satuan 0 dan 5 habis dibagi 5.

Himpunan bilangan prima terkadang dilambangkan $\mathbf {P}$ atau $\mathbb {P}$.

Sifat-sifat dasar

Faktorisasi tunggal

Artikel utama: Teorema dasar aritmetika

Suatu bilangan dapat ditulis sebagai hasil kali bilangan prima disebut faktorisasi bilangan prima. Misalnya:

${\begin{aligned}34886&=2\cdot 3\cdot 3\cdot 13\cdot 149\\&=2\cdot 3^{2}\cdot 13\cdot 149\end{aligned}}$

Bentuk yang ditulis dalam hasil kali disebut faktor bilangan prima. Faktor bilangan prima yang sama seringkali muncul lebih dari satu. Contoh di atas memiliki dua salinan faktor bilangan prima $3$. Ketika sebuah bilangan prima sering muncul berkali-kali, eksponen dapat dipakai untuk mengumpulkan salinan faktor bilangan prima. Misalnya, dalam menulis hasil kali di atas, yakni pada barisan kedua, $3^{2}$ dilambangkan sebagai tiga pangkat dua.

Pentingnya bilangan prima dalam teori bilangan dan matematika umumnya berasal dari teorema dasar aritmetika. Teorema ini mengatakan bahwa setiap bilangan bulat yang lebih besar dari 1 dapat ditulis sebagai hasil kali dari satu bilangan prima atau lebih. Lebih lanjut, hasil kalinya adalah tunggal dalam artian bahwa dua faktorisasi bilangan prima dari bilangan yang sama akan memiliki jumlah salinan yang sama dari bilangan prima yang sama meski urutannya berbeda. Walaupun ada banyak cara mencari faktorisasi melalui algoritma faktorisasi bilangan bulat, hasil yang diperoleh adalah sama. Jadi, bilangan prima dapat dianggap sebagai "satuan dasar" bilangan asli.

Bukti-bukti mengenai ketunggalan faktorisasi bilangan prima dijelaskan melalui lema Euklides: Jika $p$ bilangan prima dan $p$ membagi hasil kali $ab$ (dimana $a$ dan $b$ bilangan bulat), maka $p$ membagi $a$ atau $p$ membagi $b$ (atau membagi keduanya). Sebaliknya, jika $p$ memiliki sifat ketika dibagi hasil kalinya ($p$ selalu membagi setidaknya salah satu dari faktor hasil kali tersebut), maka $p$ haruslah bilangan prima.

Ketakterhinggaan

Artikel utama: Teorema Euklides

Ada tak berhingga banyaknya bilangan prima. Dengan kata lain, barisan bilangan prima

2, 3, 5, 7, 11, 13, ...

tidak pernah berakhir. Karena pertama kali yang membuktikan pernyataan ini adalah Euklides, pernyataan tersebut disebut teorema Euklides untuk menghormati matematikawan Yunani Kuno Euklides. Masih ada bukti mengenai ketakterhinggaan bilangan prima, diantaranya: bukti analitik oleh Euler, bukti Goldbach berdasarkan bilangan Fermat, bukti Furstenberg melalui topologi umum, dan bukti elegan Kummer.

Bukti Euler menunjukkan bahwa setiap daftar bilangan prima terhingga belum lengkap. Kunci utamanya adalah mengalikan bilangan prima pada daftar tertentu dan ditambah $1$. Jikalau terdiri dari bilangan prima $p_{1},p_{2},\ldots ,p_{n}$, maka

$N=1+p_{1}\cdot p_{2}\cdots p_{n}$.

Menurut teorema dasar aritmetika, $N$ memiliki faktorisasi bilangan prima yang faktornya berjumlah satu atau lebih.

$N=p'_{1}\cdot p'_{2}\cdots p'_{m}$

$N$ dibagi habis secara merata oleh setiap faktor-faktor tersebut, tetapi $N$ mempunyai sisa yaitu satu ketika dibagi oleh suatu bilangan prima pada daftar tertentu sehingga tidak ada faktor bilangan prima $N$ yang terdapat pada daftar tersebut. Karena tidak ada daftar bilangan prima terhingga, maka pasti ada tak berhingga banyaknya bilangan prima.

Bilangan yang dibentuk dengan menambahkan 1 pada hasil kali dari bilangan prima terkecil disebut bilangan Euklides. Lima bilangan pertama adalah bilangan prima, tetapi yang keenam,

$1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509$,

adalah bilangan komposit.

Rumus untuk bilangan prima

Artikel utama: Rumus untuk bilangan prima

Tidak ada rumus cepat yang diketahui untuk bilangan prima. Contoh, tidak ada polinomial takkonstan, bahkan dalam beberapa variabel, yang hanya memakai nilai bilangan prima. Namun, ada banyak bentuk rumus yang mengodekan semua bilangan prima, atau hanya bilangan prima. Ada rumus yang dapat didasari pada teorema Wilson, dan rumus tersebut menghasilkan 2 berkali-kali dan sisa bilangan prima dihasilkan sekali. Adapula himpunan persamaan Diophantus dalam sembilan variabel dan satu parameter dengan sifat berikut: parameter adalah bilangan prima jika dan hanya jika sistem persamaan yang dihasilkan adalah solusi bilangan asli. Hal tersebut dapat dipakai untuk memperoleh rumus tunggal dengan sifat bahwa semua nilai positif adalah bilangan prima.

Contoh rumus yang menghasilkan bilangan prima lainnya berasal dari teorema Mills dan teorema Wright. Rumus ini mengatakan bahwa terdapat suatu konstanta real $A>1$ dan $\mu$ sehingga

$\left\lfloor A^{3^{n}}\right\rfloor$ dan $\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor$

adalah bilangan prima untuk suatu bilangan asli $n$ dalam rumus yang pertama, dan suatu bilangan eksponen dalam rumus yang kedua. $\lfloor \,\cdot \,\rfloor$ merepresentasikan fungsi bilangan bulat terbesar. Akan tetapi, rumus-rumus tersebut tidak dapat digunakan untuk menghasilkan bilangan prima, karena bilangan prima harus dihasilkan terlebih dahulu agar memperoleh nilai $A$ atau $\mu$.

Pertanyaan terbuka

Banyak konjektur yang melibatkan bilangan prima telah diajukan. Seringkali memiliki perumusan dasar, banyak konjektur-konjektur tersebut memiliki bukti yang bertahan selama beberapa dekade: empat masalah Landau yang berasal dari tahun 1912 masih belum terpecahkan. Salah satu masalah Landau adalah konjektur Goldbach, yang menyatakan bahwa setiap bilangan bulat genap $n$ lebih besar dari 2 dapat ditulis sebagai jumlah dari dua bilangan prima. Hingga pada 2014, konjektur ini telah dibenarkan untuk semua bilangan hingga $n=4\cdot 10^{18}$. Pernyataan yang lebih lemah dari konjektur tersebut telah dibuktikan seperti: teorema Vinogradov yang mengatakan bahwa setiap bilangan bulat ganjil yang cukup besar dapat ditulis sebagai jumlah dari tiga bilangan prima, teorema Chen yang mengatakan bahwa setiap bilangan genap yang cukup besar dapat dinyatakan sebagai jumlah dari bilangan prima dan semiprima (hasil kali dari dua bilangan prima), serta suatu bilangan bulat genap yang lebih besar dari 10 dapat ditulis sebagai jumlah dari enam bilangan prima. Cabang teori bilangan yang mempelajari masalah tersebut disebut teori bilangan aditif.