Bilangan prima adalah bilangan bulat lebih dari 1 yang hanya habis dibagi 1 dan bilangan itu sendiri. Manusia telah mengenal bilangan prima sejak 6500 SM. Tulang Ishango yang ditemukan pada tahun 1960 (sekarang disimpan di Musee d’Histoire Naturelle di Brussels) membuktikan hal tersebut. Tulang Ishango memiliki 3 baris takik. Salah satu kolomnya memiliki 11, 13, 17, dan 19 takik, yang merupakan bilangan-bilangan prima antara 10 hingga 20.
Ada petunjuk dalam catatan bertahan Mesir kuno bahwa mereka punya pengetahuan tentang bilangan prima: di Mesir fraksi ekspansi di Rhind papirus, misalnya, memiliki bentuk yang berbeda untuk bilangan prima dan komposit. Namun, catatan awal yang masih bertahan studi eksplisit bilangan prima berasal dari Yunani Kuno. Euclid's Elements (sekitar 300 SM) berisi teorema penting tentang bilangan prima, termasuk ketidakterbatasan dari bilangan prima dan teorema dasar aritmatika. Euclid juga menunjukkan bagaimana untuk membentuk sebuah bilangan yang sempurna dari sebuah bilangan prima Mersenne.
Setelah Yunani, kecil kemungkinan terjadi dengan studi bilangan prima sampai abad ke-17. Pada tahun 1640 Pierre de Fermat menyatakan (tanpa bukti), Teorema kecil Fermat (kemudian dibuktikan oleh Leibniz dan Euler). Suatu kasus khusus teorema Fermat mungkin telah dikenal jauh lebih awal oleh Cina. Fermat menduga bahwa semua bilangan dalam bentuk 2 n + 1 adalah prima (mereka disebut angka Fermat) dan dia memverifikasikan ini ke n = 4 (atau 2 16 + 1). Namun, jumlah Fermat berikutnya 2 32 + 1 adalah komposit (salah satu faktor utama adalah 641), sebagai Euler ditemukan kemudian, dan bahkan tidak ada lagi nomor Fermat dikenal sebagai prima. Biarawan Perancis Marin Mersenne memandang bentuk bilangan prima dari 2 p - 1, dengan p prima. Kemudian bilangan tersebut disebut sebagai bilangan prima Mersenne untuk menghormatinya.
Euler bekerja di teori bilangan termasuk banyak hasil mengenai bilangan prima. Dia menunjukkan deret tak hingga 1 / 2 + 1 / 3 + 1 / 5 + 1 / 7 + 1 / 11 + ... adalah divergen. Tahun 1747 ia menunjukkan bahwa bahkan angka sempurna yang tepat dalam bentuk bilangan bulat 2 p -1 (2 p - 1), di mana faktor kedua adalah Mersenne prima.
Pada awal abad ke-19, Legendre dan Gauss secara independen menduga bahwa sebagai x cenderung, jumlah bilangan prima sampai dengan x adalah asimtot ke x / ln (x), dimana ln (x) adalah logaritma natural dari x.
Ide Riemann dalam kertas pada 1859-fungsi zeta membuat sketsa sebuah program yang akan mengarah pada bukti dari teorema bilangan prima.
Meskipun sedikit sekali manfaat yang diketahui, namun di awal masehi orang tetap mencari dan membuktikan bahwa suatu bilangan merupakan bilangan prima.
Cara yang paling efisien untuk mencari bilangan prima kecil (misalkan kurang dari 107) adalah dengan menggunakan metode Seive of Eratosthenes (240 SM) sebagai berikut :
• Daftarkanlah semua bilangan bulat antara 2 hingga n.
• Hapuslah semua bilangan kelipatan bilangan prima yang lebih kecil atau sama dengan n .
• Maka bilangan yang masih tersisa adalah bilangan prima.
Sebagai contoh, untuk mencari semua bilangan prima ≤ 30, pertama-tama didaftarkan semua bilangan bulat antara 2 hingga 30.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Bilangan pertama (= 2) adalah bilangan prima. Hapuskan semua bilangan kelipatan 2. Didapat,
2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29
Bilangan prima setelah 2 dalam daftar tersebut adalah 3, yang merupakan bilangan prima kedua. Hapus semua bilangan kelipatan 3 dari daftar. Didapat,
2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29
Bilangan setelah 3 yang belum terhapus adalah 5. Hapus semua bilangan dalah daftar yang merupakan kelipatan 5 sehingga didapat,
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Bilangan yang tidak terhapus berikutnya adalah 7 yang kuadratnya sama dengan 49 > 30. Maka bilangan yang tersisa dalam daftar merupakan himpunan semua bilangan prima ≤ 30. Pencarian bilangan prima dengan metode Sieve sangatlah mudah, cepat dan sederhana. Bahkan prosesnya tidak menggunakan operasi pembagian sama sekali. Pencarian secara langsung dengan menjalankan program di komputer bahkan lebih cepat dibandingkan dengan membaca daftar bilangan prima yang tersimpan dalam disket. Akan tetapi untuk keperluan enkripsi yang membutuhkan bilangan prima yang besar, metode Sieve dirasa tidak memadai.Sebelum komputer ditemukan, perkembangan penemuan bilangan prima masih lambat karena orang belum merasakan manfaatnya.
Ada tak terhingga banyak bilangan prima.Tertua bukti untuk pernyataan ini, kadang-kadang disebut sebagai teorema Euclid, adalah disebabkan oleh matematikawan Yunani . Euclid menyatakan hasil sebagai "ada lebih daripada yang diberikan [terbatas] jumlah bilangan prima", dan bukti pada dasarnya adalah sebagai berikut:
Mempertimbangkan set berhingga bilangan prima. Kalikan semua mereka bersama-sama dan menambahkan 1. Jumlah yang dihasilkan tidak habis dibagi oleh salah satu bilangan prima dalam himpunan berhingga kami menganggap, karena membaginya dengan semua ini akan memberikan sisa 1. Karena semua bilangan prima tidak dapat didekomposisi menjadi produk yang mendasari bilangan prima, maka baik jumlah resultan ini adalah prima itu sendiri, atau ada sebuah bilangan prima atau bilangan prima yang jumlah resultan dapat didekomposisi ke dalam tetapi tidak dalam himpunan berhingga asli dari bilangan prima. Dilain pihak,ada setidaknya satu lagi perdana yang tidak di himpunan berhingga yang akan dimulai. Argumen ini berlaku dengan tidak mempedulikan bagaimana himpunan berhingga itu dimulai. Jadi ada lebih prima daripada diberikan jumlah terbatas. Argumen sebelumnya ini menjelaskan mengapa produk banyak bilangan prima ditambah 1 harus dapat dibagi oleh beberapa perdana (kemungkinan sendiri) tidak di antara mereka banyak bilangan prima.
Buktinya kadang-kadang diungkapkan dengan cara yang salah membuat beberapa pembaca untuk berpikir bahwa P + 1 harus itu sendiri menjadi prima, dan berpikir bahwa bukti Euclid mengatakan produk utama ditambah 1 selalu prima. Kebingungan ini muncul ketika bukti tersebut disajikan sebagai bukti oleh kontradiksi dan P diasumsikan produk dari anggota sebuah himpunan berhingga yang berisi semua bilangan prima. Maka dinyatakan bahwa jika P + 1 tidak habis dibagi oleh setiap anggota yang ditetapkan, maka tidak dibagi oleh bilangan prima dan "Oleh karena itu sendiri perdana" . Ini kadang-kadang membawa pembaca untuk menyimpulkan secara keliru bahwa jika P adalah produk pertama n bilangan prima maka P + 1 adalah bilangan prima. Kesimpulan itu bergantung pada hipotesis kemudian terbukti palsu, dan tidak dapat dianggap terbukti. Counterexample yang terkecil dengan komposit P + 1 adalah
(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30.031 = 59 × 509 (keduanya prima).
Banyak lagi bukti dari bilangan prima tak terhingga dari diketahui. Menambahkan counterexample dari semua bilangan prima bersama-sama menghasilkan divergen seri tak terhingga:
Bukti pernyataan tersebut dinyatakan oleh Euler. Lebih tepatnya, jika S (x) menunjukkan jumlah dari Kebalikan dari semua bilangan prima p dengan p ≤ x, maka
S ( x ) = ln ln x + O (1) for x → ∞. S (x) = ln ln x + O (1) untuk x → ∞.
Lain bukti berdasarkan angka Fermat diberikan oleh Goldbach. Tidak hanya terdapat tak terhingga banyaknya bilangan prima, teorema Dirichlet pada progresi aritmetika menegaskan bahwa dalam setiap deret aritmetika a, a + q, a + 2 q, a + 3 q, ... di mana bilangan bulat positif a dan q coprime, ada tak terhingga banyaknya prima.
2. PENGUJIAN BILANGAN PRIMA
Untuk menggunakan bilangan prima, memverifikasi bahwa angka yang diberikan n adalah prima atau tidak adalah penting minat. Ada beberapa cara untuk mencapai tujuan ini. Sebuah saringan adalah algoritma yang menghasilkan semua bilangan prima sampai batas tertentu. Saringan tersebut yang tertua adalah saringan Eratosthenes (lihat di atas), berguna untuk bilangan prima relatif kecilModern dari Atkin saringan lebih rumit, tetapi lebih cepat ketika benar Sebelum munculnya komputer, daftar bilangan prima sampai batas seperti 10 7 juga digunakan.
Dalam praktiknya, satu sering ingin memeriksa apakah suatu bilangan prima, daripada menghasilkan daftar bilangan prima sebagai dua saringan disebutkan algoritma lakukan. Metode yang paling dasar untuk melakukan hal ini, dikenal sebagai divisi sidang, bekerja sebagai berikut: diberikan bilangan n, satu membagi n dengan semua bilangan m kurang dari atau sama dengan akar kuadrat dari jumlah tersebut Jika salah satu divisi keluar sebagai integer, maka nomor asli bukan primaSebenarnya sudah cukup untuk melakukan semua divisi untuk m sidang perdana, hanya. Sedangkan algoritma yang mudah, dengan cepat menjadi tidak praktis untuk menguji bilangan bulat besar karena jumlah faktor yang mungkin terlalu cepat tumbuh sebagai nomor-to-be-diuji meningkat: Menurut teorema bilangan prima diuraikan di bawah ini, jumlah bilangan prima kurang dari n sudah dekat n / (ln (n) - 1 Jadi, untuk memeriksa primality n untuk faktor prima terbesar yang diperlukan hanya kurang dari Sehingga jumlah calon faktor utama tersebut akan dekat dengan . Ini pernah meningkat lebih lambat dengan n, tapi, karena ada kepentingan dalam nilai-nilai yang besar untuk n, hitungan besar juga: untuk n = 10 20 itu adalah 450 juta.
Tes primality modern algoritma dapat dibagi menjadi dua kelas utama, deterministik dan probabilistik (atau "Monte Carlo") algoritma. Probabilistik algoritma dapat melaporkan nomor komposit sebagai prima, namun tentu saja tidak mengidentifikasi bilangan prima sebagai angka komposit; deterministik algoritma di sisi lain tidak memiliki kemungkinan sesat tersebut. Kepentingan algoritma probabilistik terletak pada kenyataan bahwa mereka seringkali lebih cepat daripada yang deterministik; di samping untuk kebanyakan algoritma tersebut kemungkinan keliru mengidentifikasi nomor komposit sebagai perdana yang diketahui. Mereka biasanya memilih nomor acak yang disebut "saksi" dan memeriksa beberapa rumus yang melibatkan saksi dan potensi perdana n. Setelah beberapa iterasi, mereka menyatakan n untuk menjadi "pasti komposit" atau Sebagai contoh, tes primality Fermat bergantung pada Teorema kecil Fermat (lihat di atas). Jadi, jika
a p − 1 (mod p ) p - 1 (mod p)
adalah tidak sama dengan 1, p adalah jelas komposit. . Namun, mungkin p komposit bahkan jika p - 1 = 1 (mod p) untuk semua saksi, yaitu bila p adalah Secara umum, angka komposit yang akan dinyatakan perdana mungkin tidak peduli apa pun saksi yang dipilih disebut pseudoprimes untuk masing-masing tes. Namun, yang paling populer tes probabilitas tidak menderita kelemahan ini. Waktu putar diberikan dalam bentuk n, nomor yang akan diuji dan, untuk probabilistik algoritma, jumlah k dari tes yang dilakukan.
Ada banyak jenis tertentu prima, misalnya kualifikasi oleh berbagai formula, atau dengan mempertimbangkan dengan angka decimal. Bentuk bilangan prima dari 2 p - 1, di mana p adalah bilangan prima, yang dikenal sebagai bilangan prima Mersenne. Pentingnya terletak pada kenyataan bahwa ada relatif cepat primality pengujian algoritma untuk bilangan prima Mersenne.
Prima bentuk 2 2 n + 1 yang dikenal sebagai bilangan prima Fermat, sebuah n-gon biasa adalah sejajar dan constructible menggunakan kompas jika dan hanya jika
n = 2 i • p n = 2 i • p
Di mana p adalah prima Fermat dan i adalah setiap nomor alam, termasuk nol. Hanya lima Fermat prima diketahui: 3, 5, 17, 257, dan 65.537. Bilangan prima p dimana 2 p + 1 adalah juga perdana dikenal sebagai bilangan prima Sophie Germain. Bilangan prima p disebut primorial atau perdana-faktorial jika memiliki bentuk
p = n # ± 1 p = n # ± 1 untuk beberapa nomor n, di mana n # berdiri untuk produk 2 • 3 • 5 • 7 • ... dari semua bilangan prima ≤ n.
Sebuah bilangan prima disebut faktorial jika dalam bentuk n! ± 1. Tidak diketahui apakah ada tak terhingga banyaknya primorial atau faktorial bilangan prima.
3. BILANGAN PRIMA TERBESAR YANG DIKETAHUI
Secara historis, prima terbesar yang diketahui telah hampir selalu menjadi perdana Mersenne sejak fajar komputer elektronik, karena di sana ada yang sangat cepat primality nomor tes bentuk ini, Lehmer primality Lucas-tes. Tabel berikut memberikan bilangan prima terbesar yang diketahui dari jenis yang disebutkan.
Beberapa bilangan prima terbesar yang diketahui tidak memiliki bentuk tertentu (yakni, tidak ada rumus sederhana seperti bilangan prima Mersenne yaitu) telah ditemukan dengan mengambil sepotong semi-acak data biner, mengubahnya menjadi sejumlah n, mengalikannya dengan 256 k untuk beberapa bilangan bulat positif k, dan mencari kemungkinan bilangan prima dalam interval [256 k n + 1, 256 k (n + 1) - 1].
Electronic Frontier Foundation telah menawarkan hadiah US $ 100.000 untuk penemu pertama prima dengan setidaknya 10 juta digit. Hadiah dapat diberikan kepada GIMPS dan UCLA departemen matematika untuk menemukan 47 Bilangan prima Mersenne yang dikenal. Mereka juga menawarkan $ 150.000 dan 250.000 dolar untuk 100 juta digit dan 1 milyar digit untuk masing-masing orang.
Selain hipotesis Riemann, ada banyak lagi dugaan mengenai bilangan prima, banyak yang sudah tua: misalnya, keempat masalah Landau dari 1912 (yang Goldbach, kembar perdana, Legendre dugaan dan dugaan tentang bilangan prima n 2 +1) masih terpecahkan.
Banyak dugaan berurusan dengan pertanyaan apakah suatu bilangan prima tak terhingga tunduk pada batasan-batasan tertentu ada. Hal ini menduga bahwa ada tak terhingga banyaknya bilangan prima fibonacci dan tak terhingga banyaknya bilangan prima Mersenne, tapi bukan bilangan prima Fermat. Tidak diketahui apakah ada jumlah tak terbatas perdana nomor Euclid.
Hal ini menduga bahwa ada tak terhingga banyaknya bilangan prima kembar, pasangan bilangan prima dengan perbedaan 2 (twin perdana konjektur). Polignac's dugaan adalah memperkuat dugaan itu, dinyatakan bahwa untuk setiap bilangan bulat positif n, ada tak terhingga banyaknya pasangan bilangan prima yang berurutan berbeda dengan 2 n. Hal ini menduga ada tak terhingga banyaknya bilangan prima dalam bentuk n 2 + 1. Dugaan ini adalah kasus khusus yang luas hipotesis H Schinzel. Brocard's dugaan mengatakan bahwa selalu ada setidaknya empat bilangan prima antara kuadrat berturut-turut bilangan prima lebih besar daripada 2. Legendre's dugaan menyatakan bahwa ada bilangan prima antara n 2 dan (n + 1) 2 untuk setiap bilangan bulat positif n. It is implied by the stronger Cramér's conjecture . Hal ini ditunjukkan oleh kuat dugaan Cramer.
Dugaan lain menghubungkan aspek-aspek tambahan angka dengan bilangan prima: Konjektur Goldbach menegaskan bahwa setiap bahkan integer lebih besar dari 2 dapat ditulis sebagai jumlah dari dua bilangan prima, sedangkan versi lemah menyatakan bahwa setiap bilangan ganjil lebih dari 5 dapat ditulis sebagai jumlah dari tiga bilangan prima.
Tidak ada komentar:
Posting Komentar