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

Sifat dasar

Faktorisasi unik

Artikel utama: Teorema dasar aritmetika

Menulis bilangan sebagai produk bilangan prima disebut faktorisasi prima dari bilangan tersebut. Misalnya:

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

istilah dalam produk tersebut disebut juga sebagai faktor prima. Faktor prima yang sama dapat muncul lebih dari sekali; contoh ini memiliki dua salinan faktor prima $3.$ Ketika bilangan prima muncul beberapa kali, eksponensial digunakan untuk pengelompokkan beberapa salinan dari bilangan prima yang sama: misalnya, dalam cara kedua penulisan produk atas, $3^{2}$ menunjukkan persegi atau pangkat kedua dari $3.$

Pentingnya pusat bilangan prima untuk teori bilangan dan matematika secara umum berasal dari teorema dasar aritmetika. Teorema ini menyatakan bahwa setiap bilangan bulat yang lebih besar dari 1 ditulis sebagai produk dari satu atau lebih bilangan prima. Secara sederhana, produk ini adalah unik dalam arti bahwa dua faktorisasi prima dari bilangan yang sama akan memiliki jumlah salinan yang sama dari bilangan prima yang sama, meskipun urutannya mungkin berbeda. Jadi, meskipun terdapat berbagai banyak cara yang berbeda untuk menemukan faktorisasi menggunakan algoritma faktorisasi bilangan bulat, semuanya adalah hasil yang sama. Dengan demikian bilangan prima menganggap sebagai "blok bangunan dasar" dari bilangan asli.

Beberapa bukti keunikan faktorisasi prima didasarkan pada lemma Euklides: Jika $p$ adalah bilangan prima dan $p$ membagi hasil kali $ab$ dari bilangan bulat $a$ dan $b,$ maka $p$ membagi $a$ atau $p$ membagi $b$ (atau keduanya). Sebaliknya, jika suatu bilangan $p$ memiliki sifat bahwa ketika membagi produk selalu membagi setidaknya satu faktor dari produk, maka $p$ adalah prima.

Jumlah tak hingga

Artikel utama: Teorema Euklides

Cara lain untuk mengatakan urutannya adalah

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

bilangan prima tak-akhir. Pernyataan ini disebut sebagai teorema Euklides untuk menghormati matematikawan Yunani kuno Euklides, sejak bukti pertama yang diketahui untuk pernyataan yang dikaitkan dengan dia. Banyak lagi bukti bilangan prima tak hingga yang diketahui, termasuk bukti analitis oleh Euler, bukti Goldbach berdasarkan bilangan Fermat, bukti menggunakan topologi umum Furstenberg, and Kummer's elegant proof.

Bukti Euclid menunjukkan bahwa setiap daftar hingga dari bilangan prima tak-lengkap. Ide kuncinya adalah mengalikan bilangan prima dalam daftar yang diberikan dan menambahkan $1.$ Jika daftar tersebut terdiri dari bilangan prima $p_{1},p_{2},\ldots ,p_{n},$ maka diberikan bilangan

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

Berdasarkan teorema dasar, $N$ memiliki faktorisasi prima

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

dengan satu atau lebih dari faktor prima. Maka, $N$ habis dibagi nilai rata-rata oleh faktor ini, tetapi $N$ memiliki sisa satu ketika dibagi dengan salah satu bilangan prima dalam daftar yang diberikan, jadi tidak ada faktor prima $N$ yang ada pada daftar yang diberikan. Karena tidak ada daftar hingga dari semua bilangan prima, pasti ada banyak bilangan prima.

Bilangan yang dibentuk dengan menjumlahkan satu ke hasil kali bilangan prima terkecil disebut bilangan Euklides. Lima bagian pertama adalah bilangan prima, namun untuk bagian keenam

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

adalah bilangan komposit.

Rumus bilangan prima

Artikel utama: Rumus bilangan prima

Tidak ada rumus efisien yang diketahui untuk bilangan prima. Misalnya, tidak ada polinomial non-konstan, bahkan dalam beberapa variabel mengambil hanya bilangan prima. Namun, ada banyak ekspresi yang mengkodekan semua bilangan prima atau hanya bilangan prima. Satu rumus yang mungkin didasarkan pada teorema Wilson dan menghasilkan angka 2 berkali-kali dan semua bilangan prima lainnya tepat. Ada pula satu himpunan persamaan Diophantine dalam sembilan variabel dan satu parameter dengan sifat berikut: parameter bilangan prima jika dan hanya jika sistem persamaan yang dihasilkan memiliki solusi atas bilangan asli. Hal ini digunakan untuk mendapatkan rumus tunggal dengan sifat bahwa semua nilai "positif" adalah prima.

Contoh lain dari rumus pembangkit-prima berasal dari teorema Mills dan teorema Wright. Maka ini menegaskan bahwa terdapat konstanta real $A>1$ dan $\mu$ sedemikian rupa, sehingga

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

adalah prima untuk sembarang bilangan asli $n$ dalam rumus pertama, dan sembarang bilangan eksponen dalam rumus kedua. Sehingga $\lfloor {}\cdot {}\rfloor$ mewakili fungsi lantai, bilangan bulat terbesar yang kurang dari atau sama dengan bilangan yang dimaksud. Namun, hal ini justru tidak berguna untuk menghasilkan bilangan prima, karena bilangan prima harus dibangkitkan terlebih dahulu untuk menghitung nilai $A$ atau $\mu .$

Pertanyaan terbuka

Informasi lebih lanjut: Kategori:Konjektur tentang bilangan prima

Banyak konjektur tentang bilangan prima telah diajukan. Seringkali memiliki rumus dasar, banyak dari konjektur ini telah bertahan selama beberapa dekade: keempat masalah Landau dari tahun 1912 masih belum terpecahkan. Salah satunya adalah konjektur Goldbach yang menyatakan bahwa setiap bilangan bulat genap $n$ lebih besar dari 2 ditulis sebagai jumlah dari dua bilangan prima. Hingga 2014, Konjektur ini telah diverifikasi untuk semua bilangan hingga $n=4\cdot 10^{18}.$ Pernyataan yang lebih lemah dari ini telah dibuktikan, misalnya teorema Vinogradov yang menyatakan bahwa setiap bilangan bulat ganjil besar dapat ditulis sebagai jumlah dari tiga bilangan prima. Teorema Chen menyatakan bahwa setiap bilangan genap besar dapat dinyatakan sebagai jumlah dari suatu bilangan prima dan semiprima (perkalian dari dua bilangan prima). Juga, bilangan bulat genap lebih besar dari 10 dapat ditulis sebagai jumlah dari enam bilangan prima. Cabang teori bilangan yang mempelajari pertanyaan semacam itu disebut teori bilangan aditif.

Jenis masalah lain menyangkut celah prima, perbedaan antara bilangan prima berurutan. Adanya celah prima besar secara sembarang dapat dilihat dengan memperhatikan bahwa barisan $n!+2,n!+3,\dots ,n!+n$ terdiri dari $n-1$ bilangan komposit, untuk sembarang bilangan asli $n.$ However, large prime gaps occur much earlier than this argument shows. Misalnya, celah prima pertama dengan panjang 8 adalah antara bilangan prima 89 dan 97, jauh lebih kecil dari $8!=40320.$ Diduga ada banyak sekali prima kembars, pasangan bilangan prima dengan selisih 2; ini adalah konjektur prima kembar. Konjektur Polignac menyatakan secara lebih umum bahwa untuk setiap bilangan bulat positif $k,$ ada tak hingga banyak pasangan bilangan prima berurutan yang berbeda $2k.$ Konjektur Andrica, Brocard's conjecture, Legendre's conjecture, and Oppermann's conjecture semua menyarankan bahwa jarak terbesar antara bilangan prima dari $1$ hingga $n$ paling banyak kira-kira ${\sqrt {n}},$ hasil yang diketahui mengikuti hipotesis Riemann, sedangkan konjektur Cramér lebih bertahan menetapkan ukuran celah terbesar pada $O((\log n)^{2}).$ Celah prima digeneralisasikan ke rangkap-$k$ prima, pola selisih antara lebih dari dua bilangan prima. Ketakhinggaan dan kepadatan mereka adalah subjek dari konjektur Hardy–Littlewood, yang dapat dimotivasi oleh heuristik bahwa bilangan prima berperilaku serupa dengan barisan bilangan acak dengan kerapatan yang diberikan oleh teorema bilangan prima.