Bilangan prima

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

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.

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}$.